Kenneth Rosen Edition 7 Exercise 8.3 Question 11 (Page No. 535)

Question

Give a big-O estimate for the function $f$ in question $10$ if $f$ is an increasing function.

Answer 1

By substituting we get  f(2) = 2 ;

f(4) = 3 ;

f(8) = 4 ;

and so on

therefore  f(2^k ) = k+1 ;

and f(n) = log n + 1

hence function complexity = O(log n )