In my opinion, the best case time complexity of the following code is O(1), i.e. number to be searched is found as the first element but the worst-case time complexity is O(n**2) because there can be n number of elements in each array and there can be n arrays in 2d array (nested loop to search)

Please let me know if you agree/disagree.

Note: below code is an example of an NxN array. My question is in general for NxN array and not specific to the following code.

#include <iostream>

int M[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int x = 20;

bool searchM(){
  for(int i=0;i<3;i  )
  {
    for(int j=0;j<3;j  )
    {
      if(M[i][j]==x)
      {
        return true;
      }
    }
  }
  return false;
} 

int main() {
  std::cout << searchM();
}

CodePudding user response：

If your function could search an arbitrarily-sized (instead of fixed-size) NxN matrix M, then what you're doing is a sequential search. For example:

int M[3][3] = { { 1,2,3 },{ 4,5,6 },{ 7,8,9 } };

bool searchM(int n, int x) {
    for (int i = 0; i<n; i  )
    {
        for (int j = 0; j<n; j  )
        {
            if (M[i][j] == x)
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    std::cout << searchM(3, 20) << std::endl;
}

Since the input size is N, it would be correct to say that the worst-case complexity of this algorithm is O(N²).