1 votes 1 votes 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) Algorithms time-complexity applied-gate-test-series + – devilstephen7 asked Sep 20, 2021 retagged Jul 9, 2022 by Lakshman Bhaiya devilstephen7 492 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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$) Yaman Sahu answered Sep 21, 2021 Yaman Sahu comment Share Follow See 1 comment See all 1 1 comment reply devilstephen7 commented Sep 21, 2021 reply Follow Share Thank you 0 votes 0 votes Please log in or register to add a comment.