Time Complexity of searching in unsorted matrix is linear?

Question

Given a matrix of order m X n. For searching a certain element in the matrix, the program has to parse through each element in the matrix. But, the program will still employ a nested loop. A nested loop usually implies a quadratic time complexity.

Does that mean, search is quadratic?

Or is it linear, because each element is parsed only once?

Answer 1

It's (worst case) linear, because at most it will look at each element once. One nested loop will iterate m times and one will iterate n times, which is mn elements. There are mn elements in the matrix so it's linear in terms of the number of elements in the matrix.

If it helps, think about it this way: If M is a square matrix it is still linear in terms of the number of elements in the M, but quadratic in terms of the length of a row (or column) of M.

From Wiki:

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.

In this case, we've counted the number of elementary operations by working out how many times the loop can go around at most. That number of elementary operations is the thing we care about when we compare it to the input, not necessarily how deep the looping is (although it is a good heuristic)

EDIT: a big thing that we are assuming here (it's kind of implied by your question) is that the comparison of the element can be done in constant time. If the matrix contains integers that's fine, but if it contains strings of arbitrary length or complex objects that might be a different situation indeed.