[SOLVED] data structure algorithm CSI 403 Data Structures and Algorithms Spring 2019 Homework II

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