Applied gate demo test

Question

Consider the following function int foo(int n)

{

int p = 1 ;

if (n && !(n&(n-1))) return n; while (p<n)

{

p <<= 1;

}

return p;

}

What is the worst case time complexity of function foo(n)

Answer 1

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$)

 

 

Comments

Thank you