CODEWITHSUNDEEP
algorithmbig-onested-loops
user796388
user796388

Reputation:

big oh of algorithm with nested loop

find the big oh characterization

input: n  

s<-0  
for i<-1 to n^2 do  
  for j<-1 to i do  
    s<-s+i

Both loops iterate n^2 times. I'm not sure if I should add or multiply the loops. Right now I think the answer is O(n^4).

Upvotes: 2

Views: 1131

Answers (5)

pad
pad

Reputation: 41290

Your argument is almost correct.

The number of loop iterations:

1 + 2 + ... + n^2 
= (n^2+1)*(n^2)/2
= (n^4 + n^2)/2

So the answer is Θ(n^4) (as a side note it also is O(n^4)).

You can prove that formally by choosing three constants c1, c2 and n0 such that:

c1*n^4 <= (n^4 + n^2)/2 <= c2*n^4 forall n >= n0

Upvotes: 2

Jan Zyka
Jan Zyka

Reputation: 17888

You can check simply the basic sum formula. Your sum goes not to N but N^2 which gives you

n^2(n^2+1)/2

and this is indeed O(n^4)

Upvotes: 0

phimuemue
phimuemue

Reputation: 35983

The outer loops i from 0 to n^2, while the inner one loops j from 1 to i.

Thus, the inner loop has complexity of i (inner loop needs i steps, i is varying). Let us denote the runtime of the inner loop by IL(i)=i.

To get the total runtime, we see that the inner loop is executed n^2 times with varying "parameter" i. Thus, we obtain as total runtime:

 n^2           n^2
----          ----
\     IL(i) = \    i 
/             /
----          ----
 i=1           i=1

That is, you have to sum up all numbers from 1 to n^2. There are many basic textbooks explaining how to evaluate this.

The result is (n^2)(n^2+1)/2, which leads to an overal complexity of O(n^4).

Upvotes: 4

UmNyobe
UmNyobe

Reputation: 22890

You are correct the answer is O(n^4). First the inner loop cost i. Then the outer loop cost sum(1->p) i = p(p-1)/2, where p=n^2. Which gives a cost of O(n^4)

Upvotes: 2

Daniel Kamil Kozar
Daniel Kamil Kozar

Reputation: 19286

Since the maximum value of i is n^2, that gives us O(n^2) * O(n^2) which is equal to O(n^4).

Upvotes: 0

Related Questions