1
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ Do you have any particular reason for not just using the master theorem and arriving at Θ(log^2 n)? $\endgroup$ – Jordi Vermeulen Apr 26 '15 at 20:52
  • $\begingroup$ my class doesn't cover the master theorem. Can you explain how to apply it to this problem? $\endgroup$ – MD_90 Apr 26 '15 at 21:28
  • $\begingroup$ 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. $\endgroup$ – Jordi Vermeulen Apr 26 '15 at 21:31
  • $\begingroup$ so if I have a similar problem like $T(n) = T(\frac{n}{5}) + \log(n)$ then this second rule would still apply? $\endgroup$ – MD_90 Apr 26 '15 at 21:33
  • $\begingroup$ Yes, with c = 0, k = 1, just like the problem in the question with n/3. $\endgroup$ – Jordi Vermeulen Apr 26 '15 at 21:35
4
$\begingroup$

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

Sorry for my English!

$\endgroup$
4
  • $\begingroup$ I thought log rules state that something like $3^{\log_3 n} = n$? $\endgroup$ – MD_90 Apr 27 '15 at 0:44
  • $\begingroup$ @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. $\endgroup$ – CharisAlex Apr 27 '15 at 7:12
  • $\begingroup$ Can you please tell me why you took $n=3^{k}$? $\endgroup$ – Mr. Sigma. Nov 30 '17 at 5:04
  • $\begingroup$ @Rohit. Since you know T(1) = 1 you choose this n to reach something you know and eliminate previous unknown sizes. Check also this link cs.stackexchange.com/questions/2789/… $\endgroup$ – CharisAlex Nov 30 '17 at 15:51

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.