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

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.

• This should $a_n = T(2^n)$ help! – kishlaya Feb 1 '17 at 4:44
• $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. – Ahmed S. Attaalla Feb 1 '17 at 5:16
• The edit $2$ solution is definitely false. If lg means log_10 x or even ln x. – Ahmed S. Attaalla Feb 1 '17 at 5:56
• Do you want an exact solution, or do you want an asymptotic approximation? – apnorton Feb 1 '17 at 6:09
• @AhmedS.Attaalla base 2, edited. – Bob Feb 1 '17 at 6:35

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$$