4
$\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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Feb 19, 2014 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
    Commented Feb 19, 2014 at 15:11
  • $\begingroup$ Are $n$ and $d$ independent? $\endgroup$
    – Raphael
    Commented Feb 19, 2014 at 15:14

1 Answer 1

Reset to default
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). $$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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