University:
Amherst College
Course:
COSC 311 | Algorithms
Academic year:

2017
Views:

88

Pages:

3
Author:

Alanna Stephens

SOLUTIONS Practice with Asymptotic Notation ****Turn in at the start of class on Monday. This will not be graded, and is simply for your benefit and to let me know whether the class would benefit from further review.**** Def 1. O(g(n)) = {f (n) : ∃c, n0 > 0 such that 0 ≤ f (n) ≤ c · g(n) ∀n ≥ n0 } Def 2. Ω(g(n)) = {f (n) : ∃c, n0 > 0 such that 0 ≤ c · g(n) ≤ f (n) ∀n ≥ n0 } Def 3. Θ(g(n)) = {f (n) : ∃c1 , c2 , n0 > 0 such that 0 ≤ c1 · g(n) ≤ f (n) ≤ c2 · g(n) ∀n ≥ n0 } Def 4. o(g(n)) = {f (n) : ∀c > 0, ∃n0 > 0 such that 0 ≤ f (n) < c · g(n) ∀n ≥ n0 } Def 5. ω(g(n)) = {f (n) : ∀c > 0, ∃n0 > 0 such that 0 ≤ c · g(n) < f (n) ∀n ≥ n0 } Recall that there is an easy test that can be used to compare two functions f (n) and g(n): Compute f (n) . n→∞ g(n) C = lim 1. Fill in the table: Solution: If... Then... C=0 f (n) ∈ o(g(n)) and g(n) ∈ ω(f (n)) 0 0 such that ∀n ≥ n0 , 0 ≤ c1 n ≤ f (n) ≤ c2 n. Let c1 = 4, c2 = 3, and n0 = 16. Then ∀n ≥ n0 = 16, we have f (n) = 3n + 16 ≤ 3n + n = 4n. Similarly, ∀n ≥ n0 = 16, we have f (n) = 3n + 16 ≥ 3n. Hence by definition, f (n) ∈ Θ(n). Alternative Solution: We will use the limit rule: lim n→∞ 3n + 16 16 = lim 3 + = 3. n→∞ n n Since 0 < 3 < ∞, we fall into case (2) of the above chart, so f (n) = 3n + 16 ∈ Θ(n). 1 3. Prove that Θ(loga n) = Θ(logb n) for all constants a, b > 0. Solution: Let f (n) be an arbitrary function such that f (n) ∈ Θ(loga n). Then there exist constants c1 , c2 , n0 > 0 such that ∀n ≥ n0 , 0 ≤ c1 loga n ≤ f (n) ≤ c2 loga n. But for any a, b, we have loga n = logb n . logb a 0 ≤ c1 So we have ∀n ≥ n0 , logb n log n ≤ f (n) ≤ c2 b . logb a logb a Noting that logb a is a constant, we can define c3 = c1 , logb a c4 = c2 . logb a We now have ∀n ≥ n0 , 0 ≤ c3 logb n ≤ f (n) ≤ c4 logb n. Hence by definition, f (n) ∈ Θ(logb n). Alternative Solution: Let f (n) be an arbitrary function such that f (n) ∈ Θ(loga n). Then by the limit rule, we know that lim n→∞ f (n) =C loga n for some constant C such that 0 < C < ∞. We also have loga n loga n = lim = lim loga b = loga b, n→∞ logb n n→∞ loga n/ loga b n→∞ lim and 0 < loga b < ∞. Hence we have f (n) loga n f (n) lim = lim · = n→∞ logb n n→∞ loga n logb n f (n) lim n→∞ loga n loga n lim n→∞ logb n = C · loga b, and 0 < C · loga b < ∞. Hence by the limit rule, f (n) ∈ Θ(logb n). A similar argument can be used to show that for an arbitrary f (n) ∈ Θ(logb n), it must be the case that f (n) ∈ Θ(loga n). 2 4. Prove that f (n) = 2n2 + 10 ∈ / O(n). Solution: Our proof will be by contradiction. Assume that f (n) ∈ O(n). Then by definition, there exist constants c, n0 > 0 such that ∀n ≥ n0 , 0 ≤ f (n) ≤ cn. Let n be some value such that n > n0 and n > c/2. Then f (n) = 2n2 + 10 ≥ 2n(c/2) + 10 = cn + 10 > cn. This is a contradiction. Hence our assumption is incorrect and we conclude that f (n) = 2n2 +10 ∈ / O(n). Alternative Solution: We will use the limit rule. Let g(n) = n. Then we have f (n) 2n2 + 10 10 = lim = lim 2n + = ∞. n→∞ g(n) n→∞ n→∞ n n lim This tells us that f (n) ∈ ω(g(n)); a function cannot be in both ω(g(n)) and O(g(n)), so we conclude that f (n) ∈ / O(g(n)). 3

Practice with Asymptotic Notation Solutions

Practice with Asymptotic Notation Solutions - Page 3

of 3

Description

Free up your schedule!

Take 5 seconds to unlock