algorithm

Question

sum = 0;
for( i = 0; i < n; i++)

for( j = 0; j < i*i; j++)

 

for( k = 0; k < j; k++)

 

sum++;

 

 

 

its time complexity should be o(n^3)

 1^2 +  2^2 + ------------------------------+ n^2  = n(n+1)(2n+1)/6 = o(n^3)  

 

but answer given is o(n^5) why ?

Answer 1

Comments

bhai thanks for replying and taking time to solve it thanku , i have question , when i = 0 , j = 0 , k = 0

it will execute 0 times how 1 time , loop will never exexute because condition fail hogai ??  how u took it one time

---

Yes u r right

I made mistake.

I interpreted k less than or equal to j.

I shall correct it as soon as possible

---

thanku bhai  answer is o(n^5) iam waiting hope u will post soon :)

Answer 2

Morning only I updated my answer but it is not reflected.Sorry for that.

https://stackoverflow.com/questions/7708137/running-time-of-for-loop-part-2

Comments

thanks mam , but i have done many questions , how we can directly multiply , because  j loop depends on i and k loop depends  j , so we have to unroll the loop isn't it

---

bro correct answer is o(N^5)  iam not able to generate correct series :(

---

thanku very much its helpful thanku for replying :)