Example 1.12: W Lower Bounds

The function f(n) is W (g(n)) iff there exists positive constants c and n₀

n₀ such that f(n) > cg(n) for all n, n > n₀

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

3n + 2 > 3n for n > 1

(the inequality holds for n > 0, but the definition of W requires an n₀ > 0.)

What??? The definition says “positive constants”… ooooo

3n + 3 = W (n)

100n +6 = W (n)

10n² + 4n + 2 = W (n²) as

10n² + 4n + 2 > n² for n > 1

6 * 2ⁿ + n² = W (2ⁿ) as

6 * 2ⁿ + n² > 2ⁿ for n > 1

Observe also that

3n + 3 = W (1) as

3n + 3 > 1 for n > 1

10n² + 4n + 2 = W (1) , 6 * 2ⁿ + n² = W (1) , 6 * 2ⁿ + n² = W (n¹⁰⁰)

6 * 2ⁿ + n² = W (n^50.2) , 6 * 2ⁿ + n² = W (n²) , 6 * 2ⁿ + n² = W (n)

6 * 2ⁿ + n² = W (1)