result = [] for i in n: for jj in range(len(m)): if jj < 3: result.append((n,m)) else: jj = len(m)
- m, n are two python array
- inner loop is maximum 3
Thinking
- O(n)? because inner looping is in a fixed amount
- O(n*m)?
- O(n*3)? this is not the correct way :(
What is the correct O time complexity for this?
Advertisement
Answer
Time complexity of the statement inside the inner loop is in O(1)
. Because, it is just only one comparison and one variable assignment, and computing the len(m)
is done in O(1)
. The remaining is straightforward: two nested loop with n
and m
iterations. Therefore, the time complexity is O(m * n)
.