Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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


Thanks in advance.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.