Skip to content
Advertisement

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

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

User contributions licensed under: CC BY-SA
2 People found this is helpful
Advertisement