Example 1.13: Q Theta

The function f(n) is Q(g(n)) iff there exists positive constants c₁ , c₂

and n₀ such that c₁g(n) < f(n) < c₂g(n) for all n, n > n₀

Notice – it is the same n₀

The function 3n+2 = Q (n) as

3n + 2 > 3n for n > 2 and

3n + 2 < 4n for n > 2 so c₁ = 3 , c₂ = 4, and n₀ = 2

3n + 3 = Q (n)

10n² + 4n + 2 = Q (n²)

6 * 2ⁿ + n² = Q (2ⁿ)

10 * log n + 4 = Q (log n)

Observe also that

3n + 2 != Q (1)

3n + 3 != Q (n²)

10n² + 4n + 2 != Q (n)

10n² + 4n + 2 != Q (1)

6 * 2ⁿ + n² != Q (n²)

6 * 2ⁿ + n² != Q (n¹⁰⁰)

6 * 2ⁿ + n² ! = Q (1)