0

when we do the sum of n numbers using for loop for(i=1;i<=n;i++)complexity of this is O(n), but if we do this same computation using the formula of arithmetic/geometric progression series n(n-1)/2 that time if we compute the time complexity, its O(n^2). How ? please solve my doubt.

StepUp
  • 36,391
  • 15
  • 88
  • 148
amit
  • 1
  • 1

2 Answers2

2

You are confused by what the numbers are representing.

Basically we are counting the # of steps when we talking about complexity.

n(n+1)/2 is the answer of Summation(1..n), that's correct, but different way take different # of steps to compute it, and we are counting the # of such steps.

Compare the following:

int ans = 0;
for(int i=1; i<=n;i++) ans += i;
// this use n steps only

int ans2 = 0;
ans2 = n*(n+1)/2;
// this use 1 step!!

int ans3 = 0;
for(int i=1, mx = n*(n+1)/2; i<=mx; i++) ans3++;
// this takes n*(n+1)/2 step
// You were thinking the formula would look like this when translated into code!

All three answers give the same value!

So, you can see only the first method & the third method (which is of course not practical at all) is affected by n, different n will cause them take different steps, while the second method which uses the formula, always take 1 step no matter what is n

Being said, if you know the formula beforehand, it is always the best you just compute the answer directly with the formula

shole
  • 4,046
  • 2
  • 29
  • 69
1

Your second formula has O(1) complexity, that is, it runs in constant time, independent of n.

There's no contradiction. The complexity is a measure of how long the algorithm takes to run. Different algorithms can compute the same result at different speeds.

[BTW the correct formula is n*(n+1)/2.]

Edit: Perhaps your confusion has to do with an algorithm that takes n*(n+1)/2 steps, which is (n^2 + n)/2 steps. We call that O(n^2) because it grows essentially (asymptotically) as n^2 when n gets large. That is, it grows on the order of n^2, the high order term of the polynomial.

Jerry101
  • 12,157
  • 5
  • 44
  • 63
  • means you are saying that in the formula (n(n+1)/2) sorry for minus sign) n is not consider as algorithm input size. but consider only the last number. – amit May 06 '16 at 06:33
  • 1
    Distinguish the math the program computes from the math we use to analyze how long it takes to run. A program that adds up `n` numbers will take `n` steps, independent of the numbers (assuming fixed-width integer math). That's `O(n)` complexity. A program that compares each of `n` numbers against each other will take `n*(n+1)/2` steps, which is `O(n^2)` steps [on the order of n^2] since `n^2` is a good approximation for how fast `n*(n+1)/2` grows when `n` is large. See http://stackoverflow.com/a/487278/1682419 for a graph that shows the dramatic difference between Big-O complexities. – Jerry101 May 06 '16 at 07:00