CSI 403 – Data Structures and Algorithms – Spring 2019 Homework – II
Date given: Feb. 12, 2016 Due date: Feb. 24, 2016 Note: Each problem is worth 25 points.
1. (a) Prove that n3 − 91n2 − 7n − 14 = Ω(n3). Your answer must clearly specify the constants c and n0.
(b) 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.
2. For the following pairs of functions g(n) and f(n), indicate whether g(n) is O, o, Ω or Θ of f(n). Justify your answer using rigorous arguments (simply stating the answers will result in 0 points awarded.)
(a) g(n) = √n and f(n) = (log2 n)2. (b) g(n) = n! and f(n) = nn.
3. Consider the following code segments: Code segment (A):
(a) Sum = 0;
(b) (c) (d)
for(i=0;i