Suppose we have the recurrence
$T(n) = T(\frac{n}{2}) + d$ if $n = 2^j$ and where is some integer greater than $0$ (i.e n is even). I know that this recurrence is $\Theta(lg(n))$, and I want to prove it with two inductive substitution proofs, one for $O(lg(n))$ and one for $\Omega(lg(n))$. If both proofs are successful, we have $\Theta(lg(n))$. I am still getting used to proving bounds of recurrences using the substitution method, so I would welcome and appreciate comments on incorrect steps or jumps in reasoning in my proof.
$(1) T(n) = O(lg(n)$
To prove the first part, we suppose that, for all $ n_0 < n' < n$, $T(n') \leq c lg(n)$, where $n_0$ we'll work out later. We then show that in that case $T(n) \leq c lg(n)$ . Now, if if $2n_0 \leq n$,
Our assumption gives us that
$T(\frac{n}{2}) \leq clg(\frac{n}{2})$.
By substitution, we get:
$T(n) \leq clg(\frac{n}{2}) + d$
which implies
$T(n) \leq clg(n) - c + d$
which holds for a $c$ sufficiently large to dominate the $-c + d$ term. For $n < 2n_0$, we pick $n_0 = 2$. Since $T$ is algorithmic, $T(2)$ is some positive constant. So let $c = T(2)$. Then we have $T(2) \leq c < clg(2)2$, establishing the base case.
(2) $T(n) = \Omega(lg(n)$
For this direction, we essentially go through identical reasoning but now with $\geq$ – i.e. we end with up with $T(n) \leq clg(n) - c + d$, where $c$ is suitably chosen to dominate the $-c + d$ bit.
Does this work? Do I need to consider other base cases? Have I been handwavy when saying 'let c be such that it dominates -c + d?
This is verbose, also you use the result, would be better to arrive to it.
Just set $n=2^k$ and $U(k)=T(n)$
Then since $\frac n2=2^{k-1}$ then $\ U(k)=U(k-1)+d\iff U(k)=U(0)+kd$
Now substitute back for $T$ knowing $k=\log_2(n)$ and $U(0)=T(1)$