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.

Improve this question
3
  • Does this answer your question? Time complexity of nested for-loop Commented Dec 20, 2021 at 9:40
  • It depends what the inputs you are considering are, if you mean n and m, then yes, the loop is O(N*M) Commented Dec 20, 2021 at 9:42
  • Are you assuming it takes O(1) time to convert an arbitrarily large integer to decimal and then print it? Commented Dec 20, 2021 at 9:49

5 Answers 5

Reset to default
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)

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I've added an edit to my question. This answer: stackoverflow.com/questions/526728/… contradicts yours. Any further clarification you can offer please?
@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).
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.

Improve this answer

Comments

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)

Improve this answer

1 Comment

I've added an edit to my question. This answer: stackoverflow.com/questions/526728/… contradicts yours. Any further clarification you can offer please?
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.
Improve this answer

Comments

-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)
Improve this answer

1 Comment

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.