-1

how do you solve this equation of recurrence?

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

The problem is the term $n*log_2(n)$.

Can I only consider only $n$ as it's the larger then $log_(n)$ and then solve the equations $T(n)=2T(\frac{n}{3})+n+1$?

thanks

hmakholm left over Monica
  • 286,031
Katherine Maurus
  • 199
  • 1
  • 9
  • No -- obviously the solutions are not the same, are they? – Did Jun 06 '15 at 11:17
  • @DId I don't know, and how do I solve it? – Katherine Maurus Jun 06 '15 at 11:18
  • You do not know? How comes? "and how do I solve it?" This is a different question. – Did Jun 06 '15 at 11:19
  • @Did Obviously the two equations are different but maybe they are equal asymptotically. It's possible? Anyway, how to solve the first equation? – Katherine Maurus Jun 06 '15 at 11:28
  • As usual... Forget the Master theorem, consider the change of variable $$S(k)=2^{-k}T(3^k),$$ write down a recursion between $S(k)$ and $S(k+1)$, deduce an exact formula for $S(k)$, then asymptotics for $S(k)$ when $k\to\infty$ and finally, (pretend that this allows you to) deduce asymptotics for $T(n)$ (although it does not). – Did Jun 06 '15 at 11:48
  • @Did I'm sorry but I don't understand... – Katherine Maurus Jun 06 '15 at 11:57
  • 1
    Unless you explain MUCH MORE precisely what it is you "do not understand", I am afraid I cannot be of much help. – Did Jun 06 '15 at 11:58
  • Usually I solve these equations with the Master theorem very easily using the formula $T(n)=aT(n/b) + n^s$. But in this case the term $nlog_2n$ doesn't coincide with that of the formula ($n^s$). So I don't know how to handle $nlog_2n$. I didn't understand your previous message, it seems very complicated... – Katherine Maurus Jun 06 '15 at 12:07
  • Back to "I do not understand", without any explanation. – Did Jun 06 '15 at 12:13
  • possible duplicate of Recurrence substitution method –  Jun 06 '15 at 17:01

2 Answers2

1

You must be using an impoverished version of the Master Theorem. The wording in Wikipedia, for example, applies to recurrences of the form

$$ T(n) = a T(n/b) + f(n) \qquad\qquad(a\ge 1,b>1) $$

and is perfectly applicable to your case where $f(n) = n\log n+1$. It's not restricted to $f(n)$ being a power of $n$.

The key parameter is $\log_b(a)$, which in your case is $\log_3 2 \approx 1.58$. So to find out which which case of the theorem applies, compare the growth of $n\log n+1$ with the growth of $n^{1.58}$. We find that $$ f(n) = n\log n + 1 = \mathcal O(n^{1+\epsilon}) \qquad\text{and certainly }1+\epsilon < 1.58$$ so the first case of the theorem (in Wikipedia's numbering) applies, and the result is $$ T(n) = \Theta(n^{\log_3 2}) $$

hmakholm left over Monica
  • 286,031
0

$$T(1) = 1$$ $$T(n) = 2T\left(\frac{n}{3}\right)+n \log_2(n)+1$$ Assuming that $n=3^m$, for $m\geq 0$, we have $$T\left(3^0\right) = 1$$ $$T\left(3^m\right) = 2T\left(3^{m-1}\right)+3^m \log_2\left(3^m\right)+1$$ After dividing everything by $2^m$, we have $$\frac{T\left(3^0\right)}{2^0}= \frac{1}{2^0}$$ $$\frac{T\left(3^m\right)}{2^m} = \frac{T\left(3^{m-1}\right)}{2^{m-1}}+\frac{3^m \log_2\left(3^m\right)+1}{2^m}$$ Let $S_m=\frac{T\left(3^m\right)}{2^m}$, then $$S_0= 1$$ $$S_m = S_{m-1}+\frac{3^m \log_2\left(3^m\right)+1}{2^m}$$ It follows that $$ S_m=\sum\limits_{k=0}^m \frac{3^k \log_2\left(3^k\right)+1}{2^k} $$

k170
  • 9,045