I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I don't get how $n ^{2.585}$ is ultimately derived.
Using the relationship T(n) = 6T(n/2) for n>1.
T(2) = 6T(2/2) = 6T(1) = 6
T(4) = 6T(4/2) = 6T(2) = 36
T(8) = 6T(8/2) = 6T(4) = 216
We find lg 2=1, lg 4=2, lg 8=3.
So the relationship is T(n)= $6^{lgn}$.
Induction base: For n = 1 we have initial condition
T(1) = $6^{lg1}$ = $6^0$ = 1
Induction hypothesis: Assume, for arbitrary n>1, n being a power of 2, that
T(n)= $6^{lgn}$
Induction step: Show induction hypothesis also true for the next step 2n (each step doubles n)
T(2n) = $6 ^{lg (2n)}$
To show next step, we replace n with 2n in the recurrence T(n)=6T(n/2) and use the hypothesis T(n) = $6 ^{lg n}$ , we get:
T(2n) = 6T((2n)/2) = 6T(n) = 6 . $6^{lgn}$ = $6 ^{1 + lg n}$ = $6 ^{lg 2 + lg n}$ = $6 ^{lg(2n)}$
QED
So, T (n) = $6 ^{lgn}$ = $n ^{lg6}$ = $n ^{2.585}$ Solution for the above recurrence for T(n) turns out to be $O(^{n2.585})$
Here’s the calculation in detail:
$$\large 6^{\lg n}=\left(2^{\lg 6}\right)^{\lg n}=2^{(\lg 6)(\lg n)}=2^{\lg \left(n^{\lg 6}\right)}=n^{\lg 6}$$