[Math] Program, Recurrence relation, Master-Theorem

recurrence-relations

Programming code:

    t(n)
    {
      for i=1 to n
        sum=sum+1
      if (n>1)
        sum=sum+t(n/2)+t(n/2)
      return sum
    }

I built the recurrence relation for the programming code above. I counted only the arithmetic operations.

$t(1)=n; t(n)=n + 2*2*t(n/2)$

Master-Theorem says: $a=4, b=2, c=1 => \theta(n^2)$

But Wolframalpha says $\mathcal{O}(n^3)$.

Where is my fallacy?

Best Answer

If $t(1)=1$ and $t(n)=n+4\cdot t(n/2)$ for every $n\geqslant1$ (with the mystery, which seems usual and largely neglected in the field, of the meaning of $t(x)$ when $x$ is not an integer), consider $s(k)=t(2^k)/4^k$ for every $k\geqslant0$. Then $s(0)=1$ and $s(k)=1/2^k+s(k-1)$ hence $1=s(0)\leqslant s(k)\leqslant1+1/2+1/4+\cdots\lt2$ for every $k$, in particular $4^k\leqslant t(2^k)\lt2\cdot4^k$.

Furthermore, if the sequence $(t(n))_{n\geqslant1}$ is nondecreasing (the second hypothesis seemingly always forgotten in the field), considering the unique nonnegative integer $k$ such that $2^k\leqslant n\lt2^{k+1}$, one gets $4^k\leqslant t(2^k)\leqslant t(n)\leqslant t(2^{k+1})\lt2\cdot4^{k+1}$ for every $n$, in particular $n^2/4\leqslant t(n)\lt8n^2$, which implies that $t(n)=\Theta(n^2)$.

Related Question