0

Find a tight bound for the following recurrence.

$$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 4n$$

Using the master's theorem, I have:

$$ 1 > \log{_3}{1}$$

$$k > \log{_b}{a}$$

Thus, I can conclude that $T(n) = O(n^k)$

The problem is that this seems conflicting with what I've found using substitution method.

$k = 1$ $$T(n) = T(\frac{n}{3}) + 4n$$ $k = 2$ $$T(n) = T(\frac{n}{9}) + 8n$$ $k = 3$ $$T(n) = T(\frac{n}{27}) + 12n$$ $k = 4$ $$T(n) = T(\frac{n}{81}) + 16n$$

Guessing the recurrence, I get the following

$$T(n) = T(\frac{n}{3^k}) + 4kn$$

At the base case, $\frac{n}{3^k} = 1$, thus, $n = 3^k$, and therefore, $ k = \log{_3}{n}$

Then, we have

$$T(n) = T(1) + 4n\log{_3}{n}$$ $$T(n) = 2 + 4n\log{_3}{n}$$

Doing some calculations, I can conclude that $T(n) = \theta(n\log{_3}{n})$. This causes conflict with the answer I reached from the master's theorem.

What did I do wrong?

TheValars
  • 505
  • 1
    The Master theorem would give $\Theta(n \log n)$ here: you are in Case 2. ($a=1$, $b=3$, $c=\log_b a =0$, and $k=0$) – Clement C. Nov 16 '15 at 04:22
  • I thought $4n = \theta(n^1)$? Thus in this case $k = 1$? – TheValars Nov 16 '15 at 04:25
  • 1
    Look at the exact statement of the theorem. For the "first case" to apply, you would need $f(n) = O(n^c)$ for $c < \log_b a = 0$... – Clement C. Nov 16 '15 at 04:26
  • Ah. Apologies, i seem to have misunderstood the usage of master's theorem. – TheValars Nov 16 '15 at 04:34
  • Wait, actually, if I am in case 2, how can I have both $c = 0$ and $k=0$ both. Don't you think I will need $c= 1$? If both are 0, then I would have $4n = \theta(1)$. Which is certainly false. – TheValars Nov 16 '15 at 04:45
  • You're right, I wrote too fast: it looks like here, you are in the third case, and the answer should be $\Theta(n)$ (i.e., you substitution approach was erroneous as well). To doublecheck, though -- it's late. (but something like $T(n) = 6n-5$ looks reasonable) – Clement C. Nov 16 '15 at 04:55
  • One last thing. $f(n) = 4n$ Since we have the third case, it follows that $f(n) = \theta(4n)$, does this always mean that $f(n) = \theta(n)$? – TheValars Nov 16 '15 at 05:25
  • 1
    You never put multiplicative constants in big-Oh notations: they are meant to "hide" these constants. (Look at the definition of the notation itself: one of the very points is to focus on the order of growth, ignoring the multiplicative constants.) – Clement C. Nov 16 '15 at 13:29
  • Let us continue this discussion in chat. – TheValars Nov 16 '15 at 15:30

0 Answers0