Solving (for asymptotics) of certain recurrence equations. I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. 
For example can someone help find $\Theta(T(n))$ (or solve exactly!?) for this,
$T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{6}) + \frac{n}{log(n)}$
 A: Check out Leighton's version of the Akra-Bazzi theorem. Consider a recurrence of the form:
$$
T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z))
$$
fo $z \ge z_0$, $a_k$ and $b_k$ constants, with the restrictions:

*

*There are enough base cases

*For all $k$, $a_k > 0$ and $0 < b_k < 1$

*There is a constant $c$ such that $g(z) = O(z^c)$ when $z \to \infty$

*For all $k$ it is $\lvert h_k(z) \rvert = O(z / (\log z)^2)$
Then if $p$ is such that:
$$
\sum_{1 \le k \le n} a_k b_k^p = 1
$$
the solution to the recurrence satisfies:
$$
T(z) = \Theta\left( z^p \left( 1 + \int_1^z \frac{g(u)}{u^{p + 1}} \, \mathrm{d} u \right)\right)
$$
A: Substitution works for this example.
For some $c>12$, suppose inductively that $T(n) \le \frac{cn}{\log n}$ for sufficiently large $n$.  Then we have:
\begin{align}
T(n) &= T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{6}\right)+\frac{n}{\log n} & \\
 & \le \frac{cn/2}{\log(n/2)}+\frac{cn/4}{\log(n/4)}+\frac{cn/6}{\log(n/6)}+\frac{n}{\log n} & \\
&\le \left(\frac{11(c+\epsilon)}{12}+1\right)\frac{n}{\log n} & \text{for any }\epsilon >0 \text{ for sufficiently large }n\\
&\le \frac{cn}{\log n}&\\
\end{align}
This proves that $T(n) \in O(\frac{n}{\log n})$.  Looking at the recurrence, we know that $T(n) \in \Omega(\frac{n}{\log n})$.  Therefore $T(n) \in \Theta(\frac{n}{\log n})$
