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?


$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)$


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)$

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$

  • $\begingroup$ what does "sup" mean in your limit? $\endgroup$ – user87509 Jul 26 '13 at 7:14
  • $\begingroup$ 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? $\endgroup$ – user87509 Jul 26 '13 at 7:16
  • 1
    $\begingroup$ Why do you say the first line is untrue for the second question? $\endgroup$ – Erick Wong Jul 26 '13 at 7:17
  • $\begingroup$ @positiveimpact $a_n$ is an expression which depends only on $n$, and therefore it can rightly be viewed as a function of $n$. $\endgroup$ – Erick Wong Jul 26 '13 at 7:18
  • $\begingroup$ 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$ $\endgroup$ – Angela Richardson Jul 26 '13 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy