0
$\begingroup$

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})$

$\endgroup$
1
  • $\begingroup$ The log are of base 2. $\endgroup$
    – user202729
    Apr 29, 2016 at 2:14

1 Answer 1

1
$\begingroup$

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}$$

$\endgroup$
1
  • $\begingroup$ For more symmetry you could either replace the penultimate term $2^{\lg \left(n^{\lg 6}\right)}$ by $\left(2^{\lg n}\right)^{\lg 6}$, or replace the second term $\left(2^{\lg 6}\right)^{\lg n}$ by $2^{\lg \left(6^{\lg n}\right)}$ $\endgroup$
    – Henry
    Sep 29, 2019 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.