Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
t(1)=n?? The initial condition cannot depend on n, can it? –  Did Mar 9 '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 9 '13 at 10:19
    
Note that $f(n)\in\Theta(n^2)\implies f(n)\in\mathcal{O}(n^3)$ anyway. –  Shaktal Mar 9 '13 at 10:32

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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