# T(n/3) + log(n)

how do you find the Theta of this problem... $$T(n) = T(\frac{n}{3}) + \log_2(n)$$ I end up getting a pattern of $$T(\frac{n}{3^{k}}) + \log_2(\frac{n}{3^{k-1}}) + \log_2(\frac{n}{3^{k-2}}) + ... + \log_2(n)$$ when I solve for k with T(1) = 1 I get this... $$\frac{n}{3^{k}} = 1 \\ n = 3^{k} \\ \ln n = k \ln 3 \\ k = \log_3(n)$$ then I plug into the original problem and get this... $$\log_2(\frac{n}{3^{\log_3 n}}) +log_2(\frac{n}{3^{\log_3 n - 1}}) + ... + \log_2(n)$$ I'm not sure how to proceed from this point. Any suggestions?

• Do you have any particular reason for not just using the master theorem and arriving at Θ(log^2 n)? – Jordi Vermeulen Apr 26 '15 at 20:52
• my class doesn't cover the master theorem. Can you explain how to apply it to this problem? – MD_90 Apr 26 '15 at 21:28
• Have a look at the Wikipedia page. It's basically just a set of rules for which the solution has already been proven; it doesn't work for many recurrences, but yours just so happens to fit the second case. – Jordi Vermeulen Apr 26 '15 at 21:31
• so if I have a similar problem like $T(n) = T(\frac{n}{5}) + \log(n)$ then this second rule would still apply? – MD_90 Apr 26 '15 at 21:33
• Yes, with c = 0, k = 1, just like the problem in the question with n/3. – Jordi Vermeulen Apr 26 '15 at 21:35

Actually the Master Theorem does not apply in this recurrence.The reason is that $n^{\epsilon}$ is greater than $\log(n)$ for every positive $\epsilon$, making $\log(n)$ ,for a factor $n^{\epsilon}$,polynomially less than $n^{\log_{b}a}=n^0=1$. So we have to work with the replacement method which you have done correctly. Now for $$n=3^k$$ we get $$T(n) = T(1) + \log_{2}(\frac{3^k}{3^{k-1}})+\log_{2}(\frac{3^k}{3^{k-2}})+...+\log_{2}(3^k)$$ which gives us $$T(n) = T(1)+\log_{2}(3)+\log_{2}(3^2)+...+\log_{2}(3^k)$$ which is the same as $$T(n) = T(1)+\log_{2}(3)+2\log_{2}(3)+...+k\log_{2}(3)$$ and now we see that the recurrence can easily be written as $$T(n)=T(1)+\sum_{b=1}^{k}b\log_{2}(3) \Leftrightarrow T(n)=T(1)+\log_{2}(3)\sum_{b=1}^{k}b$$ then we simply solve the summation $$T(n) = T(1) + \log_{2}(3)\frac{k(k+1)}{2}$$ we easily get $$k=\log_{3}n$$ and finally we have $$T(n) = T(1)+\log_{2}(3)\frac{\log^{2}_{3}n+log_{3}n}{2}$$ And the solution is obviously $$T(n) = \Theta(log^{2}_{3}n)$$ T(n)=T(n/5)+logn is solved accordingly
• I thought log rules state that something like $3^{\log_3 n} = n$? – MD_90 Apr 27 '15 at 0:44
• @MD_90Log rules state that $3^{\log_{3}n}=n$ but i can't see why you need something like that. It is also known that $\log_{a}x^b = b\log_{a}x$ which helps you solve the problem. Also from what i saw in the comments above you use Master Theorem all wrong, so read it again and watch some examples before trying to solve anything with it. – CharisAlex Apr 27 '15 at 7:12
• Can you please tell me why you took $n=3^{k}$? – Mr. Sigma. Nov 30 '17 at 5:04