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
    Also, if anyone would like to help tag this properly, that would be splendid. :-)2012-12-10
  • 0
    $\lim_{n\to \infty} f(n) = \infty$, not $\frac{n^2}{2}$.2012-12-10
  • 0
    @user1551 True; I didn't quite know how to say, "As n gets bigger, values of f(n) get closer to values of (n^2)/2" formally. :-)2012-12-10
  • 0
    @bythescruff In the future you could use the asymptotic notation: $f\sim g$ if $f/g \to 1.$ So here you could have wrote $f\sim n^2/2.$2012-12-10
  • 0
    @bythescruff "As n gets bigger, values of $f(n)$ get closer to values of $n^2/2$". This is formal enough, isn't it? ;-D By the way, this formal statement is false too. $f(n)$ does not get closer to $n^2/2$ when $n$ is getting large. In fact, $f(n)$ departs from $n^2/2$ more and more when $n\rightarrow\infty$. The ratio $f(n)/(n^2/2)$ does approach 1, though. As pointed out by Ragib Zaman, this is usually written as $f\sim n^2/2$.2012-12-10
  • 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
    Thanks for your answer, but embarrassingly enough, I'm having trouble working out how you get from line 1 to line 2. Can you break it down a little more for me please? It's been a long time since my physics degree... :-)2012-12-11
  • 0
    @bythescruff In the first line, we express $f(n)$ as a sum of many terms of the form $f(i) - f(i-1).$ By the relation, we know that these $f(i)-f(i-1)=i$, and putting $i$ in place of the $f(i)-f(i-1)$ gives the second line.2012-12-11
  • 0
    Aha, penny dropped now. Thanks.2012-12-12