Wsrtjtyk

I'm currently a CS undergrad enrolled in a data structures course. During the semester, we learned about big-O notation, and on one assignment, we had to write out the big-O notation of summing the numbers 1+2+3+...+n. I figured that, in the simplest method, you would be be looping from 1 to n and in each iteration adding i to the sum, so it seemed like this would be O(n) time.

I am also aware that this specific summation can be expressed as (n(n+1))/2 as a more direct way to receive the answer.

My professor insists that in both cases, the time complexity is O(n^2), and I have been emailing him back and forth hoping to get a better explanation, but he basically sends the same reply every time.

I feel like I must be misunderstanding the purpose of big-O in the first place. Even when I implement these 2 methods of finding the sum in a program and time the execution, the time of the loop method seems to increase linearly based on the size of n, and in the second method, it takes the same amount of time no matter how large n is because there is no iteration occurring in this case.

Could someone please help me understand why this would still be O(n^2)?

The answer is O(n) if you do the summation by iterating over the numbers one by one.

The answer is O(1) if you use the formula for summation directly.

Is it possible that this is a misunderstanding and that 1, 2, ..., n are time values of another operation that is performed, meaning that the time to execute that operation constantly increases, and you have to give the Big-O for this sequence of operations?

Otherwise, when the task is really just summing up all numbers from 1 to n and express that time in Big-O-notation, your opinion is correct that it is an O(n) when you take the approach looping over all elements, and using the n*(n+1)/2-formula you get even O(1).

You are computing the order of the wrong value.

As you indicated in a comment, the question does not ask what's the time complexity of doing the sum; the question asks what is the order of the sum itself. And indeed 1 +
2 + ... + n is O(n²).

In a Java example like this

int n = 1000;

int sum = 0;



// iterating n times

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

    // just a basic operation, so no extra complexity here

    sum += i;

}

the addition is called n times, so the whole code has a time complexity of O(1) * n = O(n).

If there is nothing missing in your question, O(n) will be the correct answer to the task.

Anyway, there is a good chance the professor is right ;-)

O(n * (n + 1) / 2) = O(n / 2) * O((n + 1) / 2) = O(n) * O(n + 1) = O(n) * O(n) = O(n * n) = O(n^2)