Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Programming code:

      for i=1 to n
      if (n>1)
      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|cite|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
up vote 2 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|cite|improve this answer

Your Answer


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.