Solving (for asymptotics) of certain recurrence equations.

Question

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

Answer 1

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

Answer 2

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:

1. There are enough base cases
2. For all $k$, $a_k > 0$ and $0 < b_k < 1$
3. There is a constant $c$ such that $g(z) = O(z^c)$ when $z \to \infty$
4. 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) $$