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):
$a_n$ is $O(n)$
$a_n$ is $O(n^2)$
$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):
$a_n$ is $Ω(n)$
$a_n$ is $Ω(n^2)$
$a_n$ is $Ω(n^3)$
Thanks in advance.
$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$