Suppose, that I have a four-by-four matrix and I want to print each element of it.

matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
for row in matrix
    for elem in row

So, I have a questions:

a) Should I consider, that such iterating requires O(k + n) in terms of big O notation, where k is a number of rows and n is a number of columns? I mean, $\sum_{i=1}^k1$ + $\sum_{j=1}^n1$ = O(k + n), we sum number of iterations that are required for rows and number of ones for columns. If I should not, then what is wrong with my estimates or how should I calculate big O for a matrix?

b) Can not we say, that such algorithm requires constant amount of time, because we have a well-defined input - four-by-for matrix, can we? I would like to specify what I mean: if we have constant input, does it mean, that our algo requires constant amount of time to compute in terms of big O?


1 Answer 1


For the first question

No, its actually $O(n\cdot k)$. To see why, we have two explanations.

  1. The number of elements in the matrix is $n\cdot k$ and we run through all of them

  2. The inner loop takes $O(n)$ time, but notice that we run it $k$ times. Hence, the actual summation that represents the running time is:

$$\sum_{i=1}^k\sum_{j=1}^n 1 = \sum_{i=1}^k n = O(n \cdot k)$$

For the second question

Yes, for as long as your input is well defined and with a constant size, as in this example. So actually, in this particular instance it takes $O(1)$ time. However this is usually not very interesting, since you are usually interested in more than just once matrix, or in the actual algorithm that performs the computation.

  • $\begingroup$ Thank you ever so much. Let me specify some information: if we have matrix n * k and n = k, can I state, that big O is n^2, because of their equality? $\endgroup$ Jun 19, 2021 at 14:04
  • $\begingroup$ Yes, this is totally allowed. $\endgroup$
    – nir shahar
    Jun 19, 2021 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.