Chapter 3 Answers

Asymptotic Notations

Question - 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 - 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 - 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 - 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 - Verify that for any a>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

W Omega Notation

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

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

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

Question - 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 - Which functions are in W(n²)?

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

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

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 1/n = 0

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

Q Theta Notation

Question: 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: a, b and c are > 0. How do we know that?

Show: T(n) = an² + bn + c = Q(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 (Levitin page 56)

Show that ½(n² - n) Î Q(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₂

W: 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) Î Q(n²) when c₁ = ¼, c₂ = ½ and n₀ = 2

Question - Does n²=Q(n²) imply n²=O(n²) and n²=W(n²)

Yes. See Theorem 3.1, page 46.

Little-o Notation

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

Question - Using limits show:

n²/lg n = o(n²)

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

n² ¹ o(n²)

n²/n² = 1

Question - 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-w Notation

Question

Show n²/lg n ¹ w(n²)

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

What is the n^1.9999/n²?

n^1.9999/n²=0

Is n^1.999= w(n²)?

No.

Limits

Question - Examining the limit definitions:

What is implied by f(n) / g(n) = ¥? f(n) grows much faster.

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 W? f(n) grows much faster. Also that f(n) is non-asymptotically tight.

What values do W and w have in common? ¥

What other values are shared by bounds?
W f(n) / g(n) = c for some 0 < c ≤ ¥
Q 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)=W(g(n)) and f(n)=O(g(n)) imply f(n)=Q(g(n))? Yes, though 0 and ¥ not included if f(n)=W(g(n)) and f(n)=O(g(n)).

Does f(n)=Q(g(n)) imply f(n)=W(g(n)) and f(n)=O(g(n))? Yes, though 0 and ¥ not included if f(n)=Q(g(n)).

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

Question

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= w(n²)? f(n) / g(n) = ¥ Yes.

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

Question

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. 1/3 ≤ 1/4 ≤ 2 for n³8 is false.

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

Definition of O, Q, W, o, and w by limits

W f(n) / g(n) = c for some 0 < c ≤ ¥

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

Q f(n) / g(n) = c for some 0 < c < ¥

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

w f(n) / g(n) = ¥

**Definition of O, Q, W, o, and w by limits**
W f(n) / g(n) = c for some 0 < c ≤ ¥ O f(n) / g(n) = c for some 0 ≤ c < ¥ Q f(n) / g(n) = c for some 0 < c < ¥ o f(n) / g(n) = 0 w f(n) / g(n) = ¥

Question - 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³ Î W(x²) and x³ Î w(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 - What does the example mean? O, Q, W, w, o? n²= o(2ⁿ) and n²= O(2ⁿ)

Definition of O, Q, W, o, and w by limits

W f(n) / g(n) = c for some 0 < c ≤ ¥

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

Q f(n) / g(n) = c for some 0 < c < ¥

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

w f(n) / g(n) = ¥

**Definition of O, Q, W, o, and w by limits**
W f(n) / g(n) = c for some 0 < c ≤ ¥ O f(n) / g(n) = c for some 0 ≤ c < ¥ Q f(n) / g(n) = c for some 0 < c < ¥ o f(n) / g(n) = 0 w f(n) / g(n) = ¥

Factorials

2. n! = w(2ⁿ) by inspection. Question - Explain. n!=1*2*3*...*n-1*n > 2*2*2*...*2*2 for n>3