Big O Notation explanation

Question

what is the Big O for below series

1+2+3+4+....+N

if I've to write a code for the series, it will be like

public void sum(int n){
 int sum =0;
 for(int i=1;i<=n;i++){
  sum += i;
 }
print(sum);
}

based on the above code its O(N)

Somewhere (in a udemy course) I read the order of the series is O(N square). why? enter image description here

"Somewhere I read the order is O(N square)." Where? "why?" It's not. — Andy Turner, Sep 13 '21 at 14:59
`1+2+3+4+....+N` can be computed in constant time, i.e. `O(1)` — NathanOliver, Sep 13 '21 at 14:59
Better to use the series for that calculation, anwyay. Then it's definitely O(1). — sweenish, Sep 13 '21 at 15:01
I think you're confusing the series summation with its calculation. — General Grievance, Sep 13 '21 at 15:05
The sum itself is O(n^2) – it is exactly n * (n + 1) / 2. Your code to calculate it isn't. — molbdnilo, Sep 13 '21 at 15:10
The question isn't clear. O(N^2) would be the complexity of some code *described* by these series. O(N) would be the complexity of the *naive* code (as posted) *calculating* this sum. An optimal code calculating it would be O(1). And it is really not clear what you are asking about — Eugene Sh., Sep 13 '21 at 15:14

score 0 · Answer 1 · answered Sep 13 '21 at 15:05

0

This below code has runtime O(N).

public void sum(int n){
 int sum =0;
 for(int i=1;i<=n;i++){
  sum=+i;
 }
print(sum);
}

However

O(1+2+3+...N) is O(N^2) since O(1+2+3+...N)=O(N(N+1)/2)=O(N^2).

I am guessing you are reading about the second statement and you confuse the two.

answered Sep 13 '21 at 15:05

TYeung

2,579
2
15
30

N(N+1)/2 is O(1) since it can be calculated in a constant time. Even though it has a N^2 term you don't need to iterate N^2 times. It takes a constant time to calculate the answer. – KavG Sep 13 '21 at 15:09
@GihanthaKavishka Which part? The second part is not about finding the sum of series while the first part is not about the optimal complexity but the complexity of the implementation given by OP. – TYeung Sep 13 '21 at 15:10
Yes I think I misunderstood the question. He's asking about the complexity of the series, not the algorithm. – KavG Sep 13 '21 at 15:18

Stephen C · Answer 2 · 2021-09-13T15:21:38.137

You are confusing the complexity of computing 1 + 2 + ... + N (by summing) with the result of computing it.

Consider the cost function f(N) = 1 + 2 + ... + N. That simplifies to N(N + 1)/2, and has the complexity O(N^2).

^{(I expect that you learned that sum in your high school maths course. They may even have even taught you how to prove it ... by induction.)}

On the other hand, the algorithm

public void sum(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        sum += i;
    }
    print(sum);
}

computes 1 + 2 + ... + N by performing N additions. When do a full analysis of the algorithm taking into account all of the computation, the cost function will be in the complexity class O(N).

But I can also compute 1 + 2 + ... + N with a simpler algorithm that makes use of our match knowledge:

public void sum(int n){
    print(n * (n + 1) / 2);
}

This alternative algorithm's cost function is O(1) !!!

Lesson: don't confuse an algorithm's cost function with its result.

Big O Notation explanation

2 Answers2