I'm trying to find the tight upper and lower bounds for the following recurrence:
T(n) = 2T(n/2) + 6T(n/3) + n^2, if n >= 3
= 1 if n <= 2
Drawing the recursion tree, I find that at level 2, the work done is (n^2)/2 + (2n^2)/3. The work done at level 3 is (n^2)/8 + (n^2)/6 + (n^2)/18 + (2n^2)/27.
The terms (n^2)/2 & (2n^2)/3 from level 2 of the tree and (n^2)/8 & (2n^2)/27 seem to be geometric series of odd powers.
That's all I know and I'm not sure how to proceed with this problem to find the asymptotic bounds. Any help would be greatly appreciated.
Best Answer
I think your Level $3$ is wrong: it should derive from the Level $2$ terms $2T(n/2)$ and $6T(n/3)$, not $T(n/2)$ and $T(n/3)$. So, combining the terms within each level, we have:
\begin{align} \text{Level } 1: & \qquad \qquad n^2 \\ \text{Level } 2: & \qquad \left(\frac{7}{6}\right) n^2 \\ \text{Level } 3: & \qquad \left(\frac{7}{6}\right)^2 n^2 \\ \cdots & \qquad \cdots \\ \text{Level } k: & \qquad \left(\frac{7}{6}\right)^{k-1} n^2 \\ \end{align}
A lower bound is found via the "shortest path" through the levels from $n$ to $1$:
$$n,\; n\left(\dfrac{1}{3}\right),\; n\left(\dfrac{1}{3}\right)^2,\; n\left(\dfrac{1}{3}\right)^3,\;\ldots,\; 1 = \; n\left(\dfrac{1}{3}\right)^{\log_3 n}.$$
This gives a lower asymptotic bound:
\begin{align} T(n) &\geq n^2\left( 1 + \left(\frac{7}{6}\right) + \left(\frac{7}{6}\right)^{2} + \cdots + \left(\frac{7}{6}\right)^{\log_3 n} \right) \\ &= n^2 \dfrac{\left(7/6\right)^{1+\log_3 n} - 1}{(7/6) - 1} \\ &= 7n^2 \left(7/6\right)^{\log_3 n} - 6n^2 \\ &= 7n^{2+\log_3 \left(7/6\right)} - 6n^2 \qquad\text{using $x^{\log_a y} = y^{\log_a x}$} \\ & \\ \therefore\quad T(n) &= \Omega\left( n^{2+\log_3 \left(7/6\right)} \right) \qquad\text{since $\log_3 (7/6) \gt 0$}. \end{align}
An upper bound is found via the "longest path" through the levels from $n$ to $2$ (not to $1$ since the relation is valid for $n\geq 3$):
$$n,\; n\left(\dfrac{1}{2}\right),\; n\left(\dfrac{1}{2}\right)^2,\; n\left(\dfrac{1}{2}\right)^3,\;\ldots,\; 2 = \; n\left(\dfrac{1}{2}\right)^{\log_2 n \;-\; 1}.$$
This gives an upper asymptotic bound:
\begin{align} T(n) &\leq n^2\left( 1 + \left(\frac{7}{6}\right) + \left(\frac{7}{6}\right)^{2} + \cdots + \left(\frac{7}{6}\right)^{\log_2 n \;-\; 1} \right) \\ &= n^2 \dfrac{\left(7/6\right)^{\log_2 n} - 1}{(7/6) - 1} \\ &= 6n^2 \left(7/6\right)^{\log_2 n} - 6n^2 \\ &= 6n^{2+\log_2 \left(7/6\right)} - 6n^2 \qquad\text{using $x^{\log_a y} = y^{\log_a x}$} \\ & \\ \therefore\quad T(n) &= O\left( n^{2+\log_2 \left(7/6\right)} \right) \qquad\text{since $\log_2 (7/6) \gt 0$}. \end{align}
These two bounds can be verified inductively: for some constant $c$,
\begin{align} T(n) & \geq 2c\left( \dfrac{n}{2}\right)^{2+\log_3(7/6)} + 6c\left( \dfrac{n}{3}\right)^{2+\log_3(7/6)} \\ &= cn^{2+\log_3(7/6)} \left[ \dfrac{1}{2}\cdot 2^{\log_3 (6/7)} + \dfrac{4}{7} \right] \\ &\geq cn^{2+\log_3(7/6)} \qquad\text{since $\left[ \dfrac{1}{2}\cdot 2^{\log_3 (6/7)} + \dfrac{4}{7} \right] \approx 1.025$} \\ & \\ \text{and:} \\ & \\ T(n) & \leq 2c\left( \dfrac{n}{2}\right)^{2+\log_2(7/6)} + 6c\left( \dfrac{n}{3}\right)^{2+\log_2(7/6)} + n^2 \\ &= n^{2+\log_2(7/6)} \left[ c\left(\dfrac{3}{7} + \dfrac{2}{3}\cdot 3^{\log_2 (6/7)} \right) + n^{\log_2(6/7)} \right] \\ &\geq cn^{2+\log_2(7/6)} \qquad\text{for $c\left(\dfrac{3}{7} + \dfrac{2}{3}\cdot 3^{\log_2 (6/7)} \right) + n^{\log_2(6/7)} \leq c$} \\ & \qquad\qquad\qquad\qquad\qquad\approx 0.95c + \dfrac{1}{n^{0.22}} \leq c \implies c\geq \dfrac{20}{n^{0.22}} \\ & \qquad\qquad\qquad\qquad\text{so $c = 20$ is sufficient.} \end{align}