Why is the answer O(N^2) for this big-o question?

Question

For this question:

Approximate the runtime of the following code fragment, in terms of n: Write your answer in a format such as "O(N^2)" or "O(N log N)".

int sum = 0;

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= i; j += 2) {

sum += 4;

}

}

for (int k = -50; k <= -1; k++) {

sum--;

}

Why is the answer O(N^2)? For the first for-loop, the big-o is O(N). For the next for-loop, the big-o should be O(log N), right? Because it increments by 2 each time. For the last for-loop, the big-o is O(49), which is reduced to O(1). So then, shouldn't the big-o overall be O(N) because O(N) is the largest? Please explain this to me.

Answer 1

Hello!

Everything in your assessment is correct, except for your reasoning regarding the inner for loop.

Basically the inner loop get 2 added every time with is O(n/2) -> O(n) runtime removing the constant.

Combine this with the fact it is nested in another O(n) loop and this gives you O(n^2).

A log for loop would have to multiply the iterating variable by 2 or another constant.

Examples:

i = 10.

In the above for loop we would iterate j through the following numbers: 1, 3, 5, 7, 9

This is 5 iterations total. 5 = 10/2. O(n/2) => O(n)

In a loop that multiplied by 2 we would iterate j through 1, 2, 4, 8

This is 4 iterations total. log(10) = 3, so this would be O(log(n)+1) => O(log(n)) removing the constant.

Hope this helps you understand!