Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Recurrence relation in 2 variables

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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