0

I solved the above recurrence using master theorem and applied case $2$ to solve it.

However in the final answer I have $T(n) = \Theta(\log^{(k+1)} n)$ . what should happen to $k+1$? because the final answer is $T(n) = \Theta(\log n)$

If someone has a different approach, please do share.

Elaqqad
  • 13,725
tribrick
  • 3
  • What is $k$ in $\log^{(k+1)}n$? – Math1000 Apr 05 '15 at 12:58
  • @math1000, I came across it as k>=0, I put it as =0 but didnt give the same answer as I hoped it would – tribrick Apr 05 '15 at 13:10
  • That doesn't answer the question...what does $k$ have to do with $n$? – Math1000 Apr 05 '15 at 13:11
  • @math1000 http://www.saylor.org/site/wp-content/uploads/2011/06/Master-theorem.pdf if you see page 3 , it talks about k what I told you and nothing more, I am also learning it from the internet. – tribrick Apr 05 '15 at 13:16
  • Thanks for the reference. There is no mention of $k$ in the expression $T(n)= T(2n/3) + 1$, so that reference is necessary to understand what you were talking about. – Math1000 Apr 05 '15 at 13:19
  • 1
    What goes wrong when you set $k=0$? It seems that setting $k=0$ is exactly what works. – Ben Grossmann Apr 05 '15 at 13:26

2 Answers2

4

Here we have $$T(n) = aT\left(\frac nb\right) + n^c $$ where $a=1$, $b=\frac32$, and $c=0$. Then $$\log_b a = \log_{\frac32} 1 = 0 = c,$$ so $$ T(n)\in\Theta(\log n).$$ In particular, using your reference, $k=0$ works, as $n^0\log^0 n = 1$ and $$1\in\Theta(n^0\log^0n). $$

Math1000
  • 36,983
  • I should add that I was particular in asking what $k$ is because the "master theorem" tends to have different notation depending on the author. – Math1000 Apr 05 '15 at 13:30
  • A small typo: $b=3/2$ instead of $2/3$, as o515 pointed out. – Cave Johnson Oct 26 '16 at 03:01
  • which case is applied here? I think it's case 2, the "theta" one but unsure. – mLstudent33 May 17 '20 at 00:01
  • 1
    Perhaps it is interesting to see how $$b = 3/2$$ is found. The objective is to write the numbers in this form: $$T(n) = aT\left(\frac nb\right) + n^c $$ as you can see we do not have this yet. Since we have $$T(n) = 2T(2n/3)$$ So in order to go from 2n/3 to n/.. , we do (2n/2)/(3/2), hence now we get $$T(n) = 2T(n/(3/2))$$ – TawabG May 18 '20 at 21:47
1

Here, $b=\frac32$, not $\frac23$. At first glance, the master theorem shows the inverse of $b$.

Parcly Taxel
  • 103,344
o515
  • 11