I want to determinate under which circumstances we do have $T(f(n)) = T(⌈f(n)/2⌉)+1 ∈ O(lg(f(n)))$ ( f being a function : N -> N ) i.e., that there exists c > 0 and n0 > 0 such that $T(f((x)) <= clg(f(x))$ for all $x >= n0$ using a change of a variables. ( In all the text, lg mean logarithm in base 2 ) Here is what I wrote :
Let us reason by recurrence and assume the bound to be true for all natural numbers strictly less than a given f(n) ( for a particular constant c > 0 ) and lets prove that we do have $T(f(n)) <= c*lg(f(n))$ as well . In particular the bound is therefore true for ⌈f(n)/2⌉. Therefore, we have $$T(⌈f(n)/2]) <= clg(⌈f(n)/2⌉)$$. Replacing T(⌈f(n)/2⌉)) with this value in the expression for T(f(n)) we find the following inequality: $T(f(n)) <= clg(⌈f(n)/2⌉)+1$. My goal now is to write $clg(f(n)) >= clg(⌈f(n)/2⌉)+1$ to know under which circumstances the propriety is true at rank f(n). By subtracting the two sides of the equation I arrive at the equivalent inegality $$clg(f(n))-(clg(⌈f(n)/2⌉)+1) >= 0 ≡ lg(f(n)/⌈f(n)/2⌉) >= 1/c$$, I put everything to the power of 2 to remove the lg and I arrive at the equivalent form $$f(n)/⌈f(n)/2⌉ >= 2^{(1/c)}$$ and then I am blocked here, I can write $$f(n) >= 2^{(1/c)}*⌈f(n)/2⌉$$ but I don't know what to do from here, can you help me please ? I would like to write $$f(n) >= 2^{(1/c-1)}*f(n)$$ but I guess I would loose the equivalence because 2*⌈f(n)/2⌉ is not necessary equal to f(n) ( if f(n) is odd ) and in addition to that, I would have to simplify the f(n) from the two sides to find $$1 >= 2^{(1/c-1)}$$ which completely ignore any information on f and only gives conditions on c