1
$\begingroup$

Recurrence Relation T(n)=T(n/8)+T(n/4)+lg(n)

I have been doing recurrence relations, but I just can't even get this one started. I tried iteration method, but don't think that's a good way to go about it and couldn't get anywhere. A friend told me master method should work, and another said substitution, but haven't had luck with either.

Edit: Just started learning, so assume I'm a beginner to this material.

Edit2: I've been told the answer is $n\lg(n)$ (base-2), but I still can't see how you would arrive to that.

$\endgroup$
10
  • $\begingroup$ This should $a_n = T(2^n)$ help! $\endgroup$ – kishlaya Feb 1 '17 at 4:44
  • $\begingroup$ $a_n=T(2^n)$ in the last comment does help a bit, but that leads to a linear non-homogenous recurrence whose homogenous solution pathway involves using the cubic formula. I do not think there is an easier way about going about things. $\endgroup$ – Ahmed S. Attaalla Feb 1 '17 at 5:16
  • $\begingroup$ The edit $2$ solution is definitely false. If lg means log_10 x or even ln x. $\endgroup$ – Ahmed S. Attaalla Feb 1 '17 at 5:56
  • $\begingroup$ Do you want an exact solution, or do you want an asymptotic approximation? $\endgroup$ – apnorton Feb 1 '17 at 6:09
  • $\begingroup$ @AhmedS.Attaalla base 2, edited. $\endgroup$ – Bob Feb 1 '17 at 6:35
7
$\begingroup$

If $a_n=T(2^n)$, then, for $n\geqslant3$, $$a_n=a_{n-3}+a_{n-2}+n$$ hence the series $$A(x)=\sum_{n=0}^\infty a_nx^n$$ solves $$A(x)=a_0+a_1x+a_2x^2+\sum_{n=3}^\infty(a_{n-3}+a_{n-2}+n)x^n$$ that is, $$A(x)=a_0+a_1x+a_2x^2+x^3A(x)+x^2(A(x)-a_0)+B(x)$$ with $$B(x)=\sum_{n=3}^\infty nx^n=\frac{x}{(1-x)^2}-x-2x^2$$ or equivalently, $$A(x)=\frac{C(x)}{1-x^2-x^3}$$ with $$C(x)=a_0+a_1x+(a_2-a_0)x^2+B(x)$$ Now, there exists some triplets of complex numbers $(u_k)$ and $(v_k)$ such that $$1-x^2-x^3=\prod_{k=1}^3(1-u_kx)$$ and $$\frac1{1-x^2-x^3}=\sum_{k=1}^3\frac{v_k}{1-u_kx}=\sum_{k=1}^3v_k\sum_{n=0}^\infty (u_kx)^n$$ hence $$A(x)=C(x)\sum_{n=0}^\infty\sum_{k=1}^3v_ku_k^nx^n$$ that is, for every $n\geqslant3$, $$a_n=\sum_{k=1}^3\left(a_0u_k^n+a_1u_k^{n-1}+(a_2-a_0)u_k^{n-2}+\sum_{j=3}^n ju_k^{n-j}\right)v_k$$ In particular, the radius of convergence $R$ of $A(x)$ is the zero of smallest modulus of $1-x^2-x^3$, that is, $$R\approx0.75488$$ and this implies that $$\frac{\log a_n}n\to-\log R\approx0.28120$$ In this sense, $$T(2^n)=a_n\approx R^{-n}\approx(1.3247)^n$$ hence the asymptotics $$T(n)\approx n\lg n$$ is not correct, actually one can suspect that $$T(n)\approx n^\alpha$$ with $$\alpha=-\log_2R\approx0.40568$$

$\endgroup$
2
  • $\begingroup$ (+1) Thank you for sharing this calculation with us although it is "classical" and so not really exciting for the experts here (but it is for us noobs). $\endgroup$ – user144921 Feb 3 '17 at 9:14
  • 1
    $\begingroup$ @user144921 Thanks. "Not really exciting" is offtopic here, but the fact that tons of variants of this computation are already present on the site should indeed be relevant to "you noobs"... $\endgroup$ – Did Feb 3 '17 at 13:38

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.