1
$\begingroup$

Solve the following recurrence equation using the characteristic equation.

$T(n)=2T(\frac{n}3)+\log_{3}n$ for $n>1$, $n$ a power of $3$

$T(1)=1$

I'm not quite sure I understand exactly what to do here. I've done this much on my own

Let $n=3^k$, $k=\log_{3}n$ $T(3^k)=2T(\frac{3^k}{3})+k$

$T(3^k)=2T(3^{k-1})+k$

Let $t_{k}=T(3^k)$

$t_{k}=2t_{k-1}+k$

But that's as far as I can get. After that, I'm completely lost. Even when I'm trying to follow the example in the book, it seems like either a lot of intermediate steps are skipped or the example doesn't fit my question. Any assistance would be appreciated.

$\endgroup$
  • $\begingroup$ This answers a very recent near duplicate. $\endgroup$ – Did Sep 28 '13 at 6:48
0
$\begingroup$

You have $t_k - 2t_{k-1} = k$ with the condition $t_0 = 1$ (why?)

The characteristic equation would have been $x-2 = 0$ if the equation was homogeneous (i.e. RHS was $0$). This would have given us the solution $t_k = a 2^k$. However given that there is a linear function in the RHS, we should explore solutions of form $t_k = a 2^k + (bk + c)$.

Substitute in the recurrence and see if we can find values for $b, c$ s.t. the recurrence holds for all $k$. Then use the initial condition to find $a$...

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

We can actually solve this recurrence exactly and not just for powers of three, at any rate one that is very close. Consider $$T(n) = 2 \; T(\lfloor n/3\rfloor) + \lfloor\log_3 n\rfloor+1$$ with $T(0) = 0$ and which has $T(1) = 1.$ The constant one has lower order than the logarithm so the complexity is the same as in the original query. (Note $|\lfloor\log_3 n\rfloor-\log_3 n | < 1$ and that $|\lfloor\log_3 n\rfloor+1-\log_3 n | < 1$ so adding in one introduces the same error as using the floor alone.)

The key observation is that the answer does not depend on $n$ but only on the number of digits in base three that it has, i.e. the logarithm.

If $$n= \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k \quad\text{then}\quad T(n) = \sum_{k=0}^{\lfloor\log_3 n\rfloor} 2^k \; (\lfloor\log_3 n\rfloor+1-k) = 4 \times 2^{\lfloor\log_3 n\rfloor} -\lfloor\log_3 n\rfloor -3.$$

This formula is exact for all $n.$ Now clearly the dominant term is the exponential one which gives the following complexity: $$\Theta\left(2^{\lfloor\log_3 n\rfloor}\right) = \Theta\left(3^{\log_3 2 \times \lfloor\log_3 n\rfloor}\right) = \Theta(n^{\log_3 2}).$$

This is of course the same as what the Master theorem would produce. Here is another calculation of the same type that is a bit more advanced.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Look carefully and I think you can see that $t_{n+1}$ = $t_n + 3$. Now run that observation back to T(1) = 1 $\Rightarrow t_1 = 1$. At this point you should be able to write $t_n$ just in terms of n and without any other t's.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Check your $t_n$... it must satisfy the recurrence and $t_0 = 1$. I get $t_k = 3\cdot 2^k - k - 2$. $\endgroup$ – Macavity Sep 28 '13 at 6:27

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.