Question

Asymptotic Notation. (a) [10 pts.] Prove that n3 −91n2 −7n−14 = Ω(n3). Your answer must clearly specify the constants c and n0. (b) [10 pts.] Let g(n) = 27n2 +18n and let f(n) = 0.5n2−100. Find positive constants n0, c1 and c2 such that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0. Be sure to explain how you arrived at the constants.

Answer 1

Asymptotic Notation. (a) [10 pts.] Prove that n3 −91n2 −7n−14 = Ω(n3). Your answer must clearly specify the constants c and n0. (b) [10 pts.] Let g(n) = 27n2 +18n and let f(n) = 0.5n2−100.

a) f(n) = Omega(g(n)) means there are positive constants c and n0, such that f(n) >= cg (n) for all n ≥ n0 n^3 - 91n^2 - 7n - 14 = Omega(n^3) => n^3 - 91n^2 - 7n - 14 >= c(n^3) Let's assume c = 0.5

=> n^3 - 91n^2 - 7n - 14 >= c(n^3)

=> n^3 - 91n^2 - 7n - 14 >= 0.5(n^3)

=> 0.5n^3 - 91n^2 - 7n - 14 >= 0

=> 0.5n^3 >= 91n^2 + 7n + 14

it's true for all n >= 183

so, n^3 - 91n^2 - 7n - 14 = Omega(n^3) for c = 0.5 and n0 = 183

b) c1(0.5n^2 - 100) <= 27n^2 + 18n <= c2(0.5n^2 - 100)

let's assume c1 = 1 and c2 = 56

=> c1(0.5n^2 - 100) <= 27n^2 + 18n <= c2(0.5n^2 - 100)

=> 1(0.5n^2 - 100) <= 27n^2 + 18n <= 56(0.5n^2 - 100)

=> 0.5n^2 - 100 <= 27n^2 + 18n <= 28n^2 - 5600

=> 0.5n^2 - 100 <= 27n^2 + 18n and 27n^2 + 18n <= 28n^2 - 5600

=> 0.5n^2 - 100 <= 27n^2 + 18n and 18n <= n^2 - 5600

it's true for all n >= 85 so, c1 = 1, c2 = 56 and n0 = 85