Program, Recurrence relation, Master-Theorem

Question

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?

t(1)=n?? The initial condition cannot depend on n, can it? — Did, Mar 09 '13 at 10:16
I think, you are right. It is $t(1)=1$, or? At the end, it is $\mathcal{O}(n^2)$. — user1091344, Mar 09 '13 at 10:19
Note that $f(n)\in\Theta(n^2)\implies f(n)\in\mathcal{O}(n^3)$ anyway. — Thomas Russell, Mar 09 '13 at 10:32

score 2 · Accepted Answer · answered Mar 09 '13 at 10:36

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

Program, Recurrence relation, Master-Theorem

1 Answers1