0

What is the time complexity of the following nested for loop please?

Edit. I think the answer to this question hinges on another question, to which I don't know if there is a "canonical" answer.

That question is whether the n in big-O expressions such as O(n), O(n^2) refers explicitly to an input parameter called n, or to a general value representing the size of the input.

Some of the answers given so far seem to contradict the answer given here: https://stackoverflow.com/a/23361893/3042018 I would appreciate some more clarity if possible.

for i in range(n):
    for j in range(m):
        print(i, j)  # Output statement occurs n * m times.

I'm thinking O(n^2) as each loop is O(n), but I'm wondering if it might be O(nm), and if/whether these are in fact the same thing.

Robin Andrews
  • 3,514
  • 11
  • 43
  • 111
  • Does this answer your question? [Time complexity of nested for-loop](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) – Ankit Tiwari Dec 20 '21 at 09:40
  • It depends what the inputs you are considering are, if you mean `n` and `m`, then yes, the loop is `O(N*M)` – juanpa.arrivillaga Dec 20 '21 at 09:42
  • Are you assuming it takes O(1) time to convert an arbitrarily large integer to decimal and then print it? – kaya3 Dec 20 '21 at 09:49

5 Answers5

1

You have n loops by m loops. For example for each n loop you must do m loops . That means O(n) * O(m) equal O(n*m)

user3804427
  • 432
  • 2
  • 12
  • I've added an edit to my question. This answer: https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop/23361893#23361893 contradicts yours. Any further clarification you can offer please? – Robin Andrews Dec 20 '21 at 14:05
  • @RobinAndrews The reasoning in the answer you've linked is incorrect. If n and m are independent quantities in those loops, then the runtime is O(nm) and not O(n^2). – templatetypedef Dec 20 '21 at 17:57
1

In your code, you introduce two variables, n and m. Without more information about them, the best we can do is say the time complexity is O(nm), as already stated by other answers.

You might be confused by the fact that other examples (such as in the link you posted) have more information that we can use. If we knew something else, for example that m = 2n, then we can simplify O(nm) = O(2n2) = O(n2), which might be a more informative answer for that question. However, it doesn't change the fact that your loop executes O(nm) times.

In your current algorithm description, there is nothing that tells us that we could simplify to O(n2) like you suggest. What if m is already n2? Then we get O(n3).

In general, the big-O notation does not place any requirements on what you are measuring. You decide yourself which variable or variables you want to express it in terms of. Whatever is useful to convey your message. Indeed, these variables often represent the size of the input when talking about the time complexity of algorithms, but they do not have to. They can be just numbers, given as input to the function. Or the number of bits required to represent a number given as input. As long as you define them in an unambiguous way and choose them such that they help convey your message, you're good.

Berthur
  • 4,300
  • 2
  • 14
  • 28
0

For every element in list n the whole list m is iterated. So by this said, you have m * n printings and a time complexity of O(m * n)

Christopher K
  • 37
  • 1
  • 6
  • I've added an edit to my question. This answer: https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop/23361893#23361893 contradicts yours. Any further clarification you can offer please? – Robin Andrews Dec 20 '21 at 14:05
0

@Berthur explanation is correct. But I would like to add few point for better clarification for anyone who stumble upon this post:

  1. It would be be O(n^2) if either m = n or m = c*n or n/c where "c" is some constant number.
  2. For any other case of m>n or m<n, it would be O(m*n)
  3. It can also be O(n) in case m is a constant number. Thus in O(m*n) we will ignore the value of m.
Rahul Singh
  • 195
  • 2
  • 2
  • 13
-1

The solution of this problem is o(n)

  1. because here we are simple printing the value of i & J
  2. if we do any Mathematical (addition, subtraction..etc then) answer for this problem would O(logn)
  3. If we follow any type of complex iterative then answer would be O(n^2)
Tech World
  • 35
  • 1
  • 5
  • It would be O(n) if and only if inner loop runs a constant time "m" for each iteration of n. i.e. m should be a constant value. All three points are incorrect as operation performed inside the loop does not effect the time complexity in these cases – Rahul Singh May 31 '23 at 06:51