The given problem is from CLRS, exercise 4.3-2.
Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n))
I decided to prove T(n) ≤ clog(n) and this is the result I got:
T(n)≤clog(n/2)+1
= clog(n)-clog(2)+1
= clog(n)-c+1
≤ clog(n)
From my understanding of how the substitution method and induction works is that, clog(n)-c+1 has to be smaller or equal to clog(n). Assuming n ≥ 1 and c ≥ 1, this seems to have worked from my tests. I then decided to look at solutions online, but noticed that all other solutions are proving it by adding lower order stuff. Some examples I saw where T(n) ≤ clog(n)-2, or 3log(n)-1 or clog(n)-a where a is some constant. Why would anyone want to make the problem more difficult when it can be solved without adding things to it. My question is does my solution work? If it doesn't, what is the reason for it? If possible please explain as simple as possible because I am not very good at math proofs, thank you very much!
