Chapter 3 Answers

Document last modified:

Asymptotic Notations

Question 3.1 - What is:

(1/x + 3)        3 because 1/x limit is 0

2x/10x           1/5 because x/x limit is 1

2x/10x²          0 because growth rate of x²greater than x

lg x/x²            0 because growth rate of x²greater than lg x

Question 3.2 - Why is n=O(n²) but n³≠ O(n²)?

    Because for f(n) / g(n) = c;

        n/n² = 0 = c

       n³/n² = ∞

O Big-O Notation

Question 3.3 - Which functions are in O(n²)?

n^1/2, n², n²+n²+n², n³, n^2.1? All but n³ and n^2.1

Question 3.4 - Show that 2n²+n is in O(n²).

0 ≤ h(n) ≤ cg(n)

0 ≤ 2n²+n ≤ cn²

0/n² ≤ 2n²/n²+n/n² ≤ cn²/n²Divide by n²

0 ≤ 2+1/n ≤ c 1/n = 0

0 ≤ 2+1 ≤ 3with c=3 and n₀=1

0 ≤ 3 ≤ 3

Question 3.5 - Verify that for a>0, b>0 any linear function an+b = O(n²)

0 ≤ h(n) ≤ cg(n)

0 ≤ an+b ≤ cn²

0/n² ≤ an/n²+b/n²≤ cn²

0 ≤ a/n+b/n²≤ c ⇒ 0 ≤ a+b ≤ c for n₀=1 and c=a+b

a/n = 0

b/n² = 0

Ω Omega Notation

Example - n³ = Ω(n²) with c=1 and n₀=1

Question 3.6.1 - Show using limits:

Ω f(n) / g(n) = c for some 0 < c ≤ ∞

1/n ≠ Ω(n²)
1/n/n² = 1/n³ = 0

n²/1000= Ω(n²)
n²/1000/n² = 1/1000 = 1/1000

Question 3.6.2 - Can we use n₀=0 above? No, would require c=0 but must have c>0. Also n₀ refers to problem size, a positive integer.

Question 3.6.3 - From the two graphs, is c=3 and n₀=1 the better choice? Why? Tighter bounds, 3g(n) more accurately characterizes f(n).
3n² + n = Ω(n²) with c=1 and n₀=1

3n² + n = Ω(n²) with c=3 and n₀=1

Example - ^v n = Ω(lg n) with c=1 and n₀=16

Question 3.7 - How do we know that this is true for n ≥ n₀=4? Rate of growth of lg n < ^v n

Question 3.8 - Which functions are in Ω(n²)?

n², n²+n²+n², n!, n³, n^2.1

Question 3.9 - Show that 2n²+n is in Ω(n²)

Find c

0 ≤ cg(n) ≤ h(n)

0 ≤ cn² ≤ 2n²+n

0/n² ≤ cn²/n²≤ 2n²/n²+n/n²

0≤ c≤ 2+1/n

0 ≤ c≤ 2                                c must always be ≤ 2+1/n
                                              1/n = 0
                                               so 2 ≤ 2+1/n

Find n₀

0≤ 2≤ 2+1/n₀

-2 ≤ 0≤ 1/n₀                          Satisfied by n₀ ≥ 1

What is c and n₀? c=2 and n₀=1.

Θ Theta Notation

Question 3.10 Does the following hold for ∀n ≥ n₀?

c₁n² ≤ n²/2-2n ≤ c₂n²with c₁=1/4, c₂=1/4 and n₀=8

No. 2/n = 0 so 1/4 ≤ 1/2 ≤ 1/4 is false.

Example - Recall we found a closed-end equation for the InsertionSort of T(n) = an² + bn + c.

Question 3.11 a, b and c are > 0. How do we know that?

Show: T(n) = an² + bn + c = Θ(n²)

c₁g(n) ≤ h(n) ≤ c₂g(n)

c₁n² ≤ an² + bn + c ≤ c₂n²

c₁n²/n² ≤ an²/n² + bn/n² + c/n² ≤ c₂n²/n²

c₁ ≤ a+b/n+c/n² ≤ c₂

as n → ∞, b/n, c/n² → 0

a+b/n+c/n² greatest when n₀ = 1

c₁ ≤ a+b+c when c₁ = a

a+b+c ≤ c₂when c₂ = a+b+c

Question 3.12 (Levitin page 56)

Show that ½(n² - n) ∈ Θ(n²)

Determine ∃ c₁, c₂, n₀ positive constants such that:

c₁n² ≤ ½n² - n/2 ≤ c₂n²

Divide through by n² to get

c₁ ≤ ½ - 1/2n ≤ c₂

Ω: Determine n₀ using: c₁ ≤ ½ - 1/2n

if n ≤ 1, then c₁ ≤ 0

Must have c₁ > 0

therefore, n ≥ 2, so n₀ = 2

O: Determine c₂ using: ½ - 1/2n ≤ c₂

as n → ∞, 1/2n → 0

so ½ - 1/2n → ½,

therefore c₂ ≥ ½ or c₂ = ½

Determine c₁ by plugging in n₀ = 2 into ½ - 1/2n and get ½ - ¼ = ¼
¼*2² ≤ ½*2² - ½*2 ≤ ½*2²

½(n² - n) ∈ Θ(n²) when c₁ = ¼, c₂ = ½ and n₀ = 2

Question 3.13 - Does n²=Θ(n²) imply n²=O(n²) and n²=Ω(n²)

Yes. See Theorem 3.1 of the text.

Little-O Notation

Question 3.14 What is implied by f(n) / g(n) = 0? g(n) is much larger than f(n).

Question 3.15 - Using limits show:

n²/lg n = O(n²)

(n²/lg n)/n² = 1/lg n = 0

n² ≠ O(n²)

n²/n² = 1

Question 3.16 - Classify n^2.001 and n^1.999 as O(n²) or not from the graph at right.

n^2.001 ≠ O(n²) since limit increasing to ∞ and n^1.999 = O(n²) since decreasing to 0.

Little-Ω Notation

Question 3.17

1. What is implied by f(n) / g(n) = ∞?
f(n) grows faster.

2. Show n²/lg n ≠ Ω(n²)

(n²/lg n)/n² = 1/lg n = 0

3. What is the n^1.9999/n²?

n^1.9999/n²=0

4. Is n^1.999= ω(n²)?

No.

Limits

Question 3.18 - Examining the limit definitions:

What is implied by f(n) / g(n) = c = 0 in the definition of O? g(n) grows much faster. Also that f(n) is non-asymptotically tight.

What values do O and O have in common? 0

What is implied by f(n) / g(n) = c = ∞ in the definition of ω? f(n) grows much faster. Also that f(n) is non-asymptotically tight.

What values do ω and Ω have in common? ∞

What other values are shared by bounds?
Ω f(n) / g(n) = c for some 0 < c ≤ ¥
Θ f(n) / g(n) = c for some 0 < c < ∞
                and

O f(n) / g(n) = c for some 0 ≤ c < ∞
Q f(n) / g(n) = c for some 0 < c < ∞

Does f(n)=ω(g(n)) and f(n)=O(g(n)) imply f(n)=Θ(g(n))? Yes, though 0 and ∞ not included if f(n)=ω(g(n)) and f(n)=O(g(n)).

Does f(n)=Θ(g(n)) imply f(n)=ω(g(n)) and f(n)=O(g(n))? Yes, though 0 and ∞ not included if f(n)=Θ(g(n)).

Why does it make sense to say that is Θ asymptotically tight? f(n) is only less than or greater than g(n) by some constant.

Question 3.19

Does 0 ≤ f(n) < cg(n) appear correct for n^1.999= O(n²)? f(n) / g(n) = 0 Yes.

Which of f(n) or g(n) is more efficient? f(n)

Does 0 ≤ cg(n) < f(n) appear correct for n^2.001= Ω(n²)? f(n) / g(n) = ∞ Yes.

Which of f(n) or g(n) is more efficient? g(n)

Question 3.20

In (n²/2-2n) / n² → constant - What is the constant?
n²/2n²-2n/ n² → 1/2-2/n → ½

Does the limit appear to agree with the graph? Yes.

c₁g(n) ≤ h(n) ≤ c₂g(n) with c₁=1/4, c₂=1/2 and n₀=8. What about c₁=1/3, c₂=2?
No.    21 1/3 ≤ 16 ≤ 128 is false for n=8

    1/3 n² ≤ n²/2-2n ≤ 2n²

n²/2-2n = Θ(n²), is it also O(n²) and Ω(n²)? Yes.

Definition of O, Θ, Ω, O, and Ω by limits

Ω f(n) / g(n) = c for some 0 < c ≤ ∞

O f(n) / g(n) = c for some 0 ≤ c < ∞

Θ f(n) / g(n) = c for some 0 < c < ∞

O f(n) / g(n) = 0

Ω f(n) / g(n) = ∞

**Definition of O, Θ, Ω, O, and Ω by limits**
Ω f(n) / g(n) = c for some 0 < c ≤ ∞ O f(n) / g(n) = c for some 0 ≤ c < ∞ Θ f(n) / g(n) = c for some 0 < c < ∞ O f(n) / g(n) = 0 Ω f(n) / g(n) = ∞

Question 3.21 - Compare f(n) and g(n).

f(n) = x², g(n) = x³

f(n) / g(n) = x² / x³ = 1/x  = 0

x² ∈ O(x³) and x² ∈ O(x³)

f(n) = x³, g(n) = x²

f(n) / g(n) = x³ / x² = x  = ∞

x³ ∈ Ω(x²) and x³ ∈ ω(x²)

f(n) = 2x², g(n) = x²

f(n) / g(n) = 2x² / x² = 2  = 2

2x² ∈ Q(x²)

Exponentials

Example - For all real constants a and b such that a > 1,

n^b/aⁿ = 0

The graph at right is of n²/2ⁿ

Question 3.22 - What does the example mean? O, Θ, Ω, w, O? n²= O(2ⁿ) and n²= O(2ⁿ)

Definition of O, Θ, Ω, O, and Ω by limits

ω f(n) / g(n) = c for some 0 < c ≤ ∞

O f(n) / g(n) = c for some 0 ≤ c < ∞

Θ f(n) / g(n) = c for some 0 < c < ∞

O f(n) / g(n) = 0

Ω f(n) / g(n) = ∞

**Definition of O, Θ, Ω, O, and Ω by limits**
ω f(n) / g(n) = c for some 0 < c ≤ ∞ O f(n) / g(n) = c for some 0 ≤ c < ∞ Θ f(n) / g(n) = c for some 0 < c < ∞ O f(n) / g(n) = 0 Ω f(n) / g(n) = ∞

Factorials

2. n! = ω(2ⁿ) by inspection.

Question 3.23 - Explain. n!=1*2*3*...*n-1*n > 2*2*2*...*2*2 for n>3