# Big O, Big Omega - getting this problem wrong, need understanding

I'm not sure I understand what to do here. Will someone help me understand how to determine what these recurrence relations are Big-O or Big-Omega of?

Problem

$a_0 = 0$ and $a_n = 1 + a_{n-1}$ implies $__________$

Select the possible answers (or select none):

1. $a_n$ is $O(n)$

2. $a_n$ is $O(n^2)$

3. $a_n$ is $O(n^3)$

Attempt

I see that $a_1$ is $1$, $a_2$ is $2$, and so on... I see that the expression isn't a polynomial, nor does it contain $n^1$, so is the answer "none of the above"? Is the recurrence relation Big-O of something more efficient than $O(n)$? I originally selected $O(n)$ as my answer, but that was wrong.

Big-Omega Version

$a_0 = 0$ and $a_n$ = $1 + a_{n-1}$ implies $__________$

Select correct answers (or select none):

1. $a_n$ is $Ω(n)$

2. $a_n$ is $Ω(n^2)$

3. $a_n$ is $Ω(n^3)$

$f(n)$ is $O (g(n))$ iff $\exists C, N$ such that $f(n)\leq Cg(n) \forall n>N$.

$f(n)$ is $\Omega(g(n))$ iff $\displaystyle \lim \sup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|>0$.

All three answers are true for the first question (any $C>0$ will work) and only the first is true for the second.

$a_n=1+a_{n-1}$ solves as $a_n=n$

• what does "sup" mean in your limit? – user87509 Jul 26 '13 at 7:14
• And will you identify $f(n)$ for me? I see $g(n)$ is $n$, $n^2$ or $n^3$ but what exactly is the function $f(n)$ if n is an INDEX and not a normal variable in a normal expression? – user87509 Jul 26 '13 at 7:16
• Why do you say the first line is untrue for the second question? – Erick Wong Jul 26 '13 at 7:17
• @positiveimpact $a_n$ is an expression which depends only on $n$, and therefore it can rightly be viewed as a function of $n$. – Erick Wong Jul 26 '13 at 7:18
• Supremum. $\lim \sup x_n$ is the smallest constant $c$ such that, for all $\epsilon>0$, there exists $N$ such that $x_n\leq c+\epsilon \forall n>N$ – Angela Richardson Jul 26 '13 at 7:20