Question

The function Log-Floor(x) computes the fractional part of the base-two logarithm of x (or, in other words, the largest k such that 2^k<=x). What is the asymptotic running time of the iterative implementation given below? Describe a recursive implementation of Log-Floor that has the same running time as the iterative version. Justify your solution. Provide pseudocode.

Log-Floor(x):

k = 0

while x > 1

x = x / 2 // Integer division

k = k + 1

return k

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The asympotic time is O(log2(n))

Recursive algorithm

• Function Log-Floor(x)
  • if(x<=1)
    • RETURN 0;
  • EndIf
  • Return 1+Log-Floor(x/2);
• EndFunction

It is also having O(log(n))

Kindly revert for any queries

Thanks.