# How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?

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
print(elem)


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?

## 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.

• 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? Jun 19 at 14:04
• Yes, this is totally allowed. Jun 19 at 14:41