3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 19 '14 at 14:45
  • $\begingroup$ 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. $\endgroup$ – Tom van der Zanden Feb 19 '14 at 15:11
  • $\begingroup$ Are $n$ and $d$ independent? $\endgroup$ – Raphael Feb 19 '14 at 15:14
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.