1

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?!

Anoop Dixith
  • 633
  • 2
  • 8
  • 20

4 Answers4

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.

Paul
  • 139,544
  • 27
  • 275
  • 264
  • Okay, I think I understand the point here. So, Summation(n) is actually theta(n) , isn't it?! Because, the formula just gives the final result and it's immaterial here. – Anoop Dixith Sep 14 '13 at 01:36
  • @AnoopDixith The time to calculate `Summation(n)` varies depending on how it's done, and can be done in `Θ(1)` using the closed forumla. The mathematical function `Summation` itself is `Θ(n²)`, because it's output grows proportionally to `n²`. – Paul Sep 14 '13 at 01:38
2

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).

Ben Jackson
  • 90,079
  • 9
  • 98
  • 150
1

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.

Adam Goodwin
  • 3,951
  • 5
  • 28
  • 33
0

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.

user2259824
  • 135
  • 8