# Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up:

$T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$

where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$.

By applying the Master Theorem inductively, for any particular $d$, it holds that $T(n,d)=O(n (\log{n})^d)$. However, it does not necessarily hold that $T(n,d)=O(n (\log{n})^d)$ because the constant hidden by the $O$-notation depends on the value of $d$.

I was hoping that the technically incorrect bound given by repeated application of the master theorem would be good enough. It turns out that this is actually a terrible, terrible bound. The actual values of $T(n,d)$ are orders of magnitude lower from what the asymptotic bound would predict. Does anyone know how to get a better bound?

• The Master Theorem shows that for each $d$ there exist constant $c_d,C_d$ such that for large enough $n$, $c_dn\log^d n \leq n\log^d n \leq C_dn\log^d n$. In other words, $T(n,d) = \Theta_d(n\log^d n)$. This is a tight bound up to the value of $c_d,C_d$. In particular, I don't see how the actual values of $T(n,d)$ are orders of magnitude lower. – Yuval Filmus Feb 19 '14 at 14:45
• I know that is what the Master Theorem says, but it's not strong enough of a result. I would much prefer a result of the form "There are constants $c$ and $C$ such that for all $d$...". I would like to use the asymptotic bound to predict the scalability of my algorithm and $\Theta(n\log^d{n})$ doesn't predict it very well. The algorithm runs quite fast when $n=50000,d=20$ even though $\log^{20}{50000}$ is an absolutely astronomical number ($10^{23}$). This tells us $C_d$ is incredibly small number but that's not very helpful. – Tom van der Zanden Feb 19 '14 at 15:11
• Are $n$ and $d$ independent? – Raphael Feb 19 '14 at 15:14

## 1 Answer

Suppose $T(n,d) = 2T(n/2,d) + T(n,d-1) + dn$, that $T(1,d) = d$, that $T(n,1) = n\log n$, and that $n$ is a power of $2$. Then $$T(n,d) = dn\log n + T(n,d-1) + 2T(n/2,d-1) + \dots + nT(1,d-1).$$ In particular, \begin{align*} T(n,2) &= 2n\log n + n\sum_{i=0}^{\log n} i \\ &\approx 2n\log n + \tfrac{1}{2}n\log^2n, \\ T(n,3) &\approx 3n\log n + 2n\sum_{i=0}^{\log n} i + \tfrac{1}{2}n \sum_{i=0}^{\log n} i^2 \\ &\approx 3 n\log n + n\log^2 n + \tfrac{1}{6} \log^3 n, \end{align*} and so on. More generally, we can think of $T(n,d)$ as a degree $d$ polynomial of the form $n\sum_{i=1}^d c_{d,i} \log^d n$. The coefficients are given by $c_{d,1} = d$ and $c_{d,i+1} = c_{d,i}/(i+1)$. Unrolling the recurrence, we obtain $$T(n,d) \approx n \sum_{i=1}^d \frac{d+1-i}{i!} \log^d n.$$ In particular, $$T(n,d) = \frac{1}{d!} n\log^d n + O(n\log^{d-1} n).$$