1

Looking at the example on this page, I see that we can solve the recurrence relation

T(n) = T(n-1) + O(n)

like this:

T(n) = T(n-1) + O(n)
= (T(n-2) + O(n-1)) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
...
= T(1) + O(2) + ... + O(n-1) + O(n)
= O(1 + 2 + ... + n-1 + n)
= O(n^2)

This makes pretty good sense until 

         =  O(1 + 2 + ... + n-1 + n)   
        =  O(n^2)

Why would it be O(n^2)?

Orange
  • 11
  • 2
  • Hint: Compute a simple expression (in terms of $n$) for the sum $1 + \ldots + n$. – Christopher A. Wong Oct 04 '16 at 23:33
  • The exact value of $1+2+\ldots+(n-1)+n$ is known since it is an arithmetic series. Look at the explicit formula for it. – hardmath Oct 04 '16 at 23:36
  • Christopher A. Wong, 1 + 2 + 3 = 6, which isn't 3^2. ??? – Orange Oct 04 '16 at 23:37
  • 1
    $\sum_{i=1}^ni=\frac{(n+1)n}{2} = O(n^2)$. Big O notation doesn't mean that $1+2+\cdots n = n^2$ only that it is at best asymptotically proportional. – Mosquite Oct 04 '16 at 23:46
  • $1+2+\cdots+n=\frac{1}{2}n^2+\frac{1}{2}n=O(n^2)$. (Do you know what big O notation means OP?) – anon Oct 04 '16 at 23:59
  • arctic tern, I'm very new to this type of math, but I my understanding is that Mosquite's comment means that the function ((n+1)*n) / 2 does not grow faster than the function n^2? I don't see how you would know that. – Orange Oct 05 '16 at 00:02
  • If you see $f(n)=O(g(n))$, what that means is there exists a constant $C$ such that $f(n)\le Cg(n)$ for all but finitely many $n$. Indeed, $\frac{1}{2}n^2+\frac{1}{2}n\le \frac{1}{2}n^2+\frac{1}{2}n^2=n^2$, so the value $C=1$ works. Read about it: https://en.wikipedia.org/wiki/Big_O_notation – anon Oct 05 '16 at 00:05

0 Answers0