I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.

  • $\begingroup$ There isn't much to prove.. you take the statement of the master Theorem and check whether the hypotheses needed to apply the theorem hold. Besides, this recurrence CAN be solved using the master theorem. $\endgroup$ – Steven Jan 12 at 15:45
  • $\begingroup$ @Steven OK. how should we do this? I have problem proving that n/log(n) is not polynomially smaller than n^log(2,2)! It seems clear that the two other statements of Master Theorem does not hold. $\endgroup$ – mmafshari Jan 12 at 15:53
  • $\begingroup$ See my answer.$\phantom{}$ $\endgroup$ – Steven Jan 12 at 15:57

Your recursion can be written as: $$ T(n) = aT(n/b) + f(n), $$ where $a=b=2$ and $f(n) = n \log^{-1} n$. Defining $c_{crit} = \log_b a = 1$ you can see that $f(n) = \Theta( n^{c_{crit}} \log^k n)$ for $k=-1$, therefore case 2b of the Master Theorem applies. The solution to the recurrence is therefore: $$T(n) = \Theta( n^{c_{crit}} \log \log n ) = \Theta( n \log \log n).$$

  • $\begingroup$ Very well! Thank you for your answer. Actually I didn't know about the various cases in case b of Master Theorem. All I know about Master Theorem is this. Can you help me with this? I want to show the first statement does not hold. $\endgroup$ – mmafshari Jan 12 at 16:14
  • $\begingroup$ Unfortunately I can't get why This is clearly not true since f(n) grows more than linearly :((( So stupid of me :\ I think f(n) grows less than linearly because it is divided by log(n). Maybe I'm misunderstanding the polynomially in the context :\ $\endgroup$ – mmafshari Jan 12 at 16:34
  • $\begingroup$ Ohh, sorry. It was my mistake... somehow I had $n \log n$ in my mind... give me some time to write down why $1$ does not hold. $\endgroup$ – Steven Jan 12 at 16:36
  • $\begingroup$ Thanks a million :) $\endgroup$ – mmafshari Jan 12 at 16:38
  • $\begingroup$ Let $\epsilon>0$ be any constant. We want to compare $n^{\log_b a} = n$ with $\frac{n}{\log n}$. You can do so by taking the limit of their ratio: $\lim_{n \to \infty} \frac{n^{1-\epsilon}}{n / \log n} = \lim_{n \to \infty} \frac{n \log n}{n^{1+\epsilon}} = \lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{1/n}{\epsilon n^{\epsilon-1}} = \lim_{n \to \infty} \frac{1}{\epsilon n^\epsilon} = 0$. This shows that $\frac{n}{\log n} \in \omega(n)$ and hence $\frac{n}{\log n} \not\in O(n)$. $\endgroup$ – Steven Jan 12 at 16:42

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.