Problem Detail: I’m trying to understand what is wrong with the following proof of the following recurrence $$ T(n) = 2,T!left(leftlfloorfrac{n}{2}rightrfloorright)+n $$ $$ T(n) leq 2left(cleftlfloorfrac{n}{2}rightrfloorright)+n leq cn+n = n(c+1) =O(n) $$ The documentation says it’s wrong because of the inductive hypothesis that $$ T(n) leq cn $$ What Am I missing?
Asked By : Erb
Answered By : pad
Let’s say the final goal is to prove $T(n) = mathcal{O}(n)$. You start with the induction hypothesis: $T(i) leq ci$ for all $i < n$. And to complete the proof, you have to show that $T(n) leq cn$ as well. However, what you’re able to deduce is $T(n) leq (c+1)n$, which is not helpful to complete the proof; you need one constant $c$ for (almost) all $n$. Therefore, we cannot conclude anything and $T(n) = mathcal{O}(n)$ isn’t proved. Notice that you are confused between the result and the proof process. And one more point, $T(n)$ is actually $Theta(n log n)$ in this case so you may consider an appropriate induction hypothesis to be able to prove it.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/772
