Solving a simple ${\cal O}(N\log N)$ recursive equation.

Question

A recursive divide and conquer algorithm runs for input size $N$ in $T(N)$ time where

$$ \begin{align} T(1)&={\cal O}(1) \\ T(N)&={\cal O}(1)+2T(N/2)+{\cal O}(N) \\ \end{align} $$

This should be $T(N)={\cal O}(N\log N)$. I tried the following to solve it:

$$ \begin{align} T(N)&={\cal O}(1)+2T(\frac N2)+{\cal O}(N) \\ &={\cal O}(1)+2\big( {\cal O}(1)+2T(\frac N4)+{\cal O}(N/2)\big) +{\cal O}(N) \\ &={\cal O}(1)+2\Big( {\cal O}(1)+2\big({\cal O}(1)+2T(\frac N8)+{\cal O}(N/4)\big)+{\cal O}(N/2)\Big) +{\cal O}(N) \\ &=(4+2+1){\cal O}(1)+8T(\frac N8)+4{\cal O}(\frac N4)+2{\cal O}(\frac N2)+{\cal O}(N) \\ \text {after }i \text{ times} \\ &= (2^i-1){\cal O}(1)+2^iT(\frac N{2^i})+2^{i-1}{\cal O}(\frac N{2^{i-1}})+2^{i-2}{\cal O}(\frac N{2^{i-2}})+\ldots+2{\cal O}(\frac N2)+{\cal O}(N) \\ \text{use }i=\log_2N \\ &=(N-1){\cal O}(1)+N{\cal O}(1)+\frac N2{\cal O}(2)+\frac N4{\cal O}(4)+\ldots+2{\cal O}(\frac N2)+{\cal O}(N) \end{align} $$

Now the first two summands are obviously ${\cal O}(N)$, but I’m at loss for the remaining summands.

How do I lead the remaining summands into ${\cal O}(N \log N)$? And did I make a mistake somewhere?

Answer 1

Unfortunately, you're being too loose. Because the number of terms in the sum (where I've fixed the errors in your substitution)

$$\frac{N}{1} \mathcal{O}(1) + \frac{N}{2} \mathcal{O}(2) + \frac{N}{4} \mathcal{O}(4) + \cdots + 1 \mathcal{O}(N) $$

is not constant but depends on $N$, the sum could turn out to be anything at all if the hidden constants behave sufficiently pathologically.

You really should translate the problem out of big-oh notation to do the analysis, and then back into big-oh notation at the end.

Answer 2

I think I got it now. If we look at $$ \frac N1{\cal O}(1)+\frac N2{\cal O}(2)+\frac N4{\cal O}(4)+\ldots+4{\cal O}(\frac N4)+2{\cal O}(\frac N2)+1{\cal O}(N) $$ we can make certain that each summand is ${\cal O}(N)$. That yields $$ {\cal O}(N)+{\cal O}(N)+\ldots+{\cal O}(N)+{\cal O}(N) $$ Now the question remains how many summands there are.

Assume $N$ is a power of $2$. Then there exist $\log_2 N$ summands.

That’s $\log_2 N*{\cal O}(N)={\cal O}(N\log N)$.

Answer 3

Rewriting this equation without big O notation: $$\begin{align} T(1)&=e \\ T(n)&=2T(\frac n2)+cn+d \end{align} $$ where $c$, $d$, $e$ are constant.

Substituting a couple times: $$\begin{align} T(n)&=2T\left(\frac n2\right)+cn+d \\ &=2\left(2T\left(\frac n{2^2}\right)+c\frac n2+d\right)+cn+d \\ &=2\left(2\left(2T\left(\frac n{2^3}\right)+c\frac n{2^2}+d\right)+c\frac n2+d\right)+cn+d \\ &=2^3T\left(\frac n{2^3}\right)+\frac{2^2}{2^2}cn+\frac 22cn+cn+2^2d+2d+d \\ &=2^iT\left(\frac n{2^i}\right)+icn+\sum_{k=0}^{i-1}2^kd \\ &=2^iT\left(\frac n{2^i}\right)+icn+\frac{2^i-1}{2-1}d \\ &=ne+(\log_2n)cn+(n-1)d \end{align} $$ Because $c$, $d$, $e$ are constant this is ${\cal O}(n\log n)$.

Answer 4

Considering the Master Theorem, http://en.wikipedia.org/wiki/Master_theorem, which is used specifically for determining the run-times of divide and conquer algorithms, first note that as $$T(n) = aT(n/b) + f(n), \qquad a \geq 1, b > 1$$ and your recurrence relation is $$T(n)={\cal O}(1)+2T(n/2)+{\cal O}(n) = 2T(n/2)+{\cal O}(n),$$ it follows that $a = 2,b=2,c=1$ and so $c = 1 = \log_2 2$. Taking $k = 0$, we are in Case 2 shown in the wikipedia entry I linked earlier. Hence $$T(n) = {\cal O}(n^c \log^{k+1}n) = {\cal O}(n\log n).$$