GATEFORUM

Question

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

       for(j=0;j<=i²;j++){

             for(k=0;k<=$\frac{n}{2}$;k++){

                   x=y+z;

}}}

How many times the x=y+z statement will execute?

          

Comments

i = 1 ,  2 ,   3 ,  4 ,  5 , 6 ,  7 ,  8 ,  9,.............................n

j = 1² , 2², 3², 4² ,5², 6², 7², 8², 9²,.............................n²

k = 1, $\frac{n}{2}$, $\frac{n}{2}$,$\frac{n}{2}$,$\frac{n}{2}$$\frac{n}{2}$$\frac{n}{2}$,.........

Total =  $\frac{n}{2}$ ( 1² + 2² + 3² + 4² + 5² + 6² + 7² + 8² + 9²,............................ + .n² ​​​​​)

        =  $\frac{n}{2}$ (n(2n+1)(n+1)/3)

---

@Prashant. your j calculation is wrong. It should be n^2 + 1

Answer 1

Here we need to consider the innermost loop which runs for (n/2+1) = O(n)  times always as it runs from k = 0 to k = n/2 regardless of value of 'i' and 'j' which represent outer two loops .

Now we have to see how many times 'j' runs . Here 'j' is dependent on 'i' . Hence for each 'i' value , we compute number of times 'j' runs and then we sum it up to find number of times 'j' runs in total.

So for i = 0 , number of times 'j' runs  =  0 + 1

         i = 1 ,  number of times 'j' runs  =  1² + 1

         i = 2 ,  number of times 'j' runs  =  2² + 1

.......  i = n , number of times 'j' runs   =  n² + 1

Hence number of times 'j' runs           =  1² + 2² ............ + n²  +  1 + 1 + 1 .....(n+1 times)

                                                       =  n(n+1)(2n+1) / 6  + (n+1)

                                                       =  O(n³)

Hence number of times 'k' runs in total   =   O(n³) * O(n)

                                                           =  O(n⁴)

Hence required time complexity             =  O(n⁴)

Comments

expression x=y+z

for n=2 loop will execute 16 times,

for n=3 loop will execute  36 times,

for n=4 loop will execute 105 times,

for n=5 loop will execute 183 times

but when i put the values of 'n' in your expression the answer is incorrect  for n>=3.

---

the answer is asympiotically equal to n⁴ , ie, the values for n will be greater than n³ and less than n⁵. Hope its clear now.

---

@dixit bishwash

this is because there is fractional value when j is running from 0 to n/2,

i have done my calculations assuming n/2 everywhere, but think what if n=21 then floor(n/2) = 10, it will make large diffrences for larger values...

but the answer will be correct if n will be even