retagged by
492 views

1 Answer

1 votes
1 votes
int foo(int n)

{

    int p = 1 ;

    if (n && !(n&(n-1))) // When n = 1 or n = 0 then condition is true otherwise false
        return n; 

    while (p<n)
    {
        p <<= 1;//Its equivalent to p * 2^i  where i = 1 to n-1
    }

    return p;

} 

Therefore in worst case

$^{2^{k-1}}$ < n

Taking log on both sides 

$k-1 = \log_{2} n$

Therefore T(n) = O($\log_{2} n$)

 

 

Related questions

1 votes
1 votes
1 answer
1
LRU asked Nov 2, 2021
365 views
What is the correct order ?
2 votes
2 votes
1 answer
2
LRU asked Nov 3, 2021
815 views
The time required to determine the minimum element from the max heap of size O(log(n)) is given by
5 votes
5 votes
1 answer
3
LRU asked Nov 5, 2021
647 views
Given the following undirected graph, the cost of the minimal spanning tree of the graph is ____.
0 votes
0 votes
2 answers
4
rsansiya111 asked Nov 2, 2022
1,171 views
In the GO back N ARQ sender is sending the 15 packets to the destination with a window size of 5.Assume every sixth packet while transmission is lost. How many transmiss...