For loop time complexity (i=1; i<=n*n; i++)

Question

I have a question regarding time complexity for a for loop. Would this still be O(n)

for (int i = 1; i <= 2*n; i++) {
    //statement;
}

Also would this be O(n²)

for (i = 1; i <= n*n; i++) {
    //stament;
}

Tried looking everywhere for this example but couldn’t find one. Also, why would the counter have an effect of the time complexity if it were incrementing anything other than by 1.

What do you think the complexities would be, and why? How does the number of operations in each of those loops change when `n` changes? (I'm assuming the number of operations is a useful substitute for time.) — ilkkachu, Apr 14 '22 at 22:03
@RobertM The first complexity is O( n ) and the second is O( n^2 ). — Vlad from Moscow, Apr 14 '22 at 22:04
The time complexity of your code also depends on what's _inside the loop!_ For example, if you had _another_ `for i=1 to n` loop inside the `for i=1 to 2n` loop, the time complexity would be O(n^2). Also what does your question have to do with c++ (other than the fact that you've shown part of a valid c++ `for` statement)? — Pranav Hosangadi, Apr 14 '22 at 22:30

score 1 · Answer 1 · edited Apr 14 '22 at 23:21

To understand this,first understand what exactly is the time complexity. Time complexity in simple terms is basically how your output grows with the increase in input size. It is not how much time an algorithm takes.

Part-1:

Yes, the complexity Big Oh will still be O(N). One main reason for this is we ignore constants. For example, if we have k*n times where k is any positive number, k will be ignored because it is a constant. And if we talk about O(N) or O(2N), they both show linear growth.

Part-2:

Yes in case of n*n. The complexity will be O(N**2) because if we judge on definition premise, the growth is Quadratic. For every input size, the graph is growing quadratically.

Part-3

Suppose counter is incrementing 2 times instead of 1. Then the complexity will be n / 2 or we can write it ((1/2) * n), 1/2 is constant (k). So, can ignored. Therefore, in this case, time complexity will be O(n).

Hope, this answer your question!

For loop time complexity (i=1; i<=n*n; i++)

1 Answers1