1,038 views
4 votes
4 votes

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

       for(j=0;j<=i2;j++){

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

                   x=y+z;

}}}

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

          

1 Answer

Best answer
1 votes
1 votes

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  =  12 + 1

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

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

Hence number of times 'j' runs           =  12 + 22 ............ + n2  +  1 + 1 + 1 .....(n+1 times)

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

                                                       =  O(n3)

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

                                                           =  O(n4)

Hence required time complexity             =  O(n4)

selected by

Related questions

1 votes
1 votes
0 answers
1
newdreamz a1-z0 asked Jan 18, 2019
337 views
i have 1 doubt regarding the initialization of highlighted portion.Will the value of ’k’ change at each iteration or it will remain same (whatever value assigned to i...
0 votes
0 votes
1 answer
2
TusharKumar asked Dec 22, 2022
510 views
can anyone explain how the for loop works here..?