2.29

Results

1. f(n)=n²+3n+4 vs g(n)=6n+7
     n² dominates n, so for sufficiently large n we have f(n) ≥ c·g(n) with c > 0, while f(n) cannot be bounded above by a constant·g(n).
     ⇒ f(n)=Ω(g(n))
2. f(n)=n√n = n^3/2 vs g(n)=n²−n = Θ(n²)
     n^3/2 grows strictly slower than n², so f(n) ≤ c·g(n) for some constant c, but f(n) is not bounded below by g(n).
     ⇒ f(n)=O(g(n))
3. f(n)=2ⁿ−n² vs g(n)=n⁴+n² = Θ(n⁴)
     2ⁿ dominates any polynomial, so f(n) ≥ c·g(n) eventually, and no constant can upper-bound f(n) by g(n).
     ⇒ f(n)=Ω(g(n))

Back to Chapter 2