recategorized by
1,642 views

2 Answers

Best answer
6 votes
6 votes

Here the key thing is :

k is initialised only once outside while loop

So lets analyse for different values of 'i'..

When  i = 0 , i.e. first loop iteration , k runs logn times [ as we have right shift operation which is same as division by 2 ]

So eventually k becomes 1 and it exits from inner loop..

From next value of 'i' , i.e. next outer loop iteration , since 'k' is not reinitialised so condition "k > 1" is checked which becomes false so it does not enter into inner loop at all..

So is the case for all upcoming values of 'i'..

Hence time complexity  =  O(logn) + O(1) .....[n-1] times

                                    =  O(logn) + n - 1

                                    =  O(n)

Hence the time complexity of the given program should be O(n) ..

selected by
3 votes
3 votes
K = n.

For i = 0,

         While loop will run for ($log_{2}$ N) times as in every iteration k becomes half.

         Now k becomes 0 and while loop becomes false.

For i = 1,

         As k = 0, while will run 1 times.

For i = 2, Same 1 times.

.....

.....

For i = n, 1 times.

T(n) = (log n) + 1 + 1 + 1 ........ (n-1 times 1).

T(n) = O(n).

Related questions

4 votes
4 votes
1 answer
1
1 votes
1 votes
0 answers
2
kartikeya2812 asked Jun 16, 2018
387 views
What will be the time complexity of the following algorithm ?A(n){if(n<=1) return 1;for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } }}
5 votes
5 votes
0 answers
3
Mk Utkarsh asked Jan 9, 2018
407 views
T(n) $\leq$ T($\frac{n}{5}$) + T($\frac{7n}{10}$) + 15nT(n) $\leq$ 5 when n $<$ 6