Exercise 1: Asymptotic Notations

Besides the upper bound represented by big-O notation, 4 other asymptotic notations are defined in Chapter 3 (pay attention to where ≤ is used vs. <).

Lower bound (big-Omega):

Ω(g(n)) = {f(n) : there exist positive constants c and n₀ such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n₀}

Upper bound, not tight (little-o):

o(g(n)) = {f(n) : for any positive constant c, there exists a positive constant n₀ such that 0 ≤ f(n) < cg(n) for all n ≥ n₀}

Note: n₀ may depend on c, i.e., possibly a different n₀ for each c

Alternately, $\underset{n\to \mathrm{\infty }}{lim}\frac{f\left(n\right)}{g\left(n\right)}=0$

Lower bound, not tight (little-omega):

ω(g(n)) = {f(n) : for any positive constant c, there exists a positive constant n₀ such that 0 ≤ cg(n) < f(n) for all n ≥ n₀}

Note: n₀ may depend on c, i.e., possibly a different n₀ for each c

Alternately, $\underset{n\to \mathrm{\infty }}{lim}\frac{f\left(n\right)}{g\left(n\right)}=\mathrm{\infty }$

Tight bound (big-Theta):

Θ(g(n)) = {f(n) : there exist positive constants c₁,c₂ and n₀ such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀}

To complete this graded assignment, reply with an analysis of the following function:

f(n) = 2n⁵ + 3n² + 4

1. Choose and determine one of the 4 notations for f(n). For example, if you were to do big-O (not an allowed choice), then O(n⁷) would be one possible answer.
2. Then, prove it, explaining how you came up with your answer (i.e., show your work).
   • To prove big-Omega, find a c and n₀.
   • To prove little-o or little-omega, it is easier to find the limit of f(n)/g(n), though you can also show that there is an n₀ that works for all c.
   • To prove big-Theta, find a c₁, c₂ and n₀.
3. Reply to another poster with a short critique of their determined notation and proof.

You may wish to use the tools introduced in Topic 1b: Asymptotic Analysis Online Lecture.