Description
1 Written assignment
1. Order Notation
(a) Suppose f(n) = Θ(g(n)). Prove formally that f(n)+nlogn = Θ(g(n)+nlogn). (b) State whether or not f(n) is O(g(n)), f(n) is Ω(g(n)), f(n) is Θ(g(n)), f(n) is o(g(n)), and f(n) is ω(g(n)). For each case above give a yes/no answer and a brief justification. f(n) = n4 logn n+2 and g(n) = n4−2n3 5n2 . (c) State whether or not f(n) is O(g(n)), f(n) is Ω(g(n)), f(n) is Θ(g(n)), f(n) is o(g(n)), and f(n) is ω(g(n)). For each case above give a yes/no answer and a brief justification. f(n) = n3−1/logn and g(n) = n3. (d) 2. Suppose f1(n) ≥ 0 is Θ(g(n)) and f2(n) ≥ 0 is Θ(g(n)). Prove or give a counterexample:
(a) f1(n) + f2(n) is Θ(g(n)) (b) f1(n)−f2(n) is O(1) (c) f1(n)/f2(n) is Θ(1)
3. Analyze the following pieces of pseudocode and for each of them give a tight (Θ) bound on the running time as a function of n. Show you work. Note: lg(n) is defined as the discrete logarithm base 2, i.e. the floor of log2(n) + 1.
(a) for i = 1 to n for j = 1 to lg(n) for k = 1 to 19 x = x + 1
1
(b) for i = 1 to n for j = 1 to i^3 for k = 1 to n x = x + 1 (c) i = n while(i 1) for j = 1 to n x = x + 1 if i is odd i = i – 1 else i = i/2 (d) i = n while(i 2) for j = 1 to n x = x + 1 i = sqrt(i)
4. You are asked to compute the number bn for n a nonnegative integer. The straightforward solution is to compute the iterated product b×b×…×b from left to right, which takes time Θ(n). Give a divide-and-conquer algorithm for the same problem that takes time Θ(logn).
