4
$\begingroup$

Software engineer here; I've written a little program which demonstrates that for the following function:

$f(n+1) = f(n)+n+1$

starting with

$f(0)=0$

the following is true:

$\lim_{n\to \infty}\left(f(n)\right) = \frac{n^2}{2}$

and therefore the Big-O notation which best describes the function is $O(n^2)$. I have no idea how to prove it formally, though. Can anyone help?

  • 0
    Ah yes, of course. Sloppy thinking on my part. Clearly I need to hang out in here more. :-)2012-12-11

1 Answers 1

8

We can write the relation as $f(n+1) - f(n ) = n+1.$ Thus, $ f(n) = (f(n) - f(n-1) ) + (f(n-1) - f(n-2) ) + \cdots + (f(1) - f(0) ) + f(0) $

$ = n+ (n-1) + (n-2) + \cdots +1 = \frac{n(n+1)}{2}.$

  • 0
    Aha, penny dropped now. Thanks.2012-12-12