What is the Time Complexity of this code sample? like nested loop, but inner loop is a fixed number

Tags: , ,



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?

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



Source: stackoverflow