How is Summation(n) Theta(n^2) according to its formula but Theta(n) ij we just look at it as a single for loop?

Question

Our prof and various materials say Summation(n) = (n) (n+1) /2 and hence is theta(n^2). But intuitively, we just need one loop to find the sum of first n terms! So, it has to be theta(n).I'm wondering what am I missing here?!

Answer 1

All of these answers are misunderstanding the problem just like the original question: The point is not to measure the runtime complexity of an algorithm for summing integers, it's talking about how to reason about the complexity of an algorithm which takes i steps during each pass for i in 1..n. Consider insertion sort: On each step i to insert one member of the original list the output list is i elements long, thus it takes i steps (on average) to perform the insert. What is the complexity of insertion sort? It's the sum of all of those steps, or the sum of i for i in 1..n. That sum is n(n+1)/2 which has an n^2 in it, thus insertion sort is O(n^2).

Answer 2

The running time of the this code is Θ(1) (assuming addition/subtraction and multiplaction are constant time operations):

result = n*(n + 1)/2 // This statement executes once

The running time of the following pseudocode, which is what you described, is indeed Θ(n):

result = 0
for i from 1 up to n:
    result = result + i // This statement executes exactly n times

Here is another way to compute it which has a running time of Θ(n²):

result = 0
for i from 1 up to n:
    for j from i up to n:
        result = result + 1 // This statement executes exactly n*(n + 1)/2 times

All three of those code blocks compute the natural numbers' sum from 1 to n.

This Θ(n²) loop is probably the type you are being asked to analyse. Whenever you have a loop of the form:

for i from 1 up to n:
    for j from i up to n:
        // Some statements that run in constant time

You have a running time complexity of Θ(n²), because those statements execute exactly summation(n) times.

Answer 3

I think the problem is that you're incorrectly assuming that the summation formula has time complexity theta(n^2).

The formula has an n^2 in it, but it doesn't require a number of computations or amount of time proportional to n^2.

Summing everything up to n in a loop would be theta(n), as you say, because you would have to iterate through the loop n times.

However, calculating the result of the equation n(n+1)/2 would just be theta(1) as it's a single calculation that is performed once regardless of how big n is.

Answer 4

Summation(n) being n(n+1)/2 refers to the sum of numbers from 1 to n. Which is a mathematical formula and can be calculated without a loop which is O(1) time. If you iterate an array to sum all values that is an O(n) algorithm.