Description

Part I
Compute the exact number of times that the statement tick is executed in the following pseudocode fragments, as a function of n. Show your work, including for each loop the minimum and maximum value of the loop counter as a function of n and/or the next outermost counter. Give your answer in closed form, with no remaining summations. Work must be shown to receive full credit.
Reminder: what is “pseudocode”? It is a way of expressing algorithms that describes at a high level what they do but omits details specific to any particular language (Java, C, Python, etc.). You’ll find lots of pseudocode in your textbook. If you have any question about what the code blocks below mean, please ask.
1. for j in 1 … n do for k in 0 … j + 5 do tick
2. i ← 0
while i < n do tick
j ← n
while j > i do tick tick j−−
i++
3. tick i ← 1 while i ≤ n do tick
j ← 0
while j < i × i do tick
j++ i++
Part II
Answer each of the following questions. Justify your answers using either the definitions of O, Ω, and Θ or the techniques shown in class (along with basic math).
4. Does 5 · (n + 2)2 = Ω(nlogn)?
5. Does 8log2n+log2 log2n = Ω(n3)?
6. Does nlog16 n = O(nlnn)?
7. Does (3n2 − 10n) = Θ(n2)?
8. Does nlogn = Ω(n11/8)?
9. Let f(n) and g(n) be non-negative functions of n. Prove using the definitions of O, Ω, and Θ — not using limit tests — that if g(n) = Ω(f(n)), then f(n) + g(n) = Θ(g(n)).
10. Let f(n) and g(n) be non-negative functions of n.
If f(n) = Θ(g(n)), does f(n)/g(n) = Θ(1)? Justify your answer.
Part III
Every night, AT&T has to update its database of every customer’s telephone number. To enable fast lookups, the database includes an index that is a sorted list of all its phone numbers. This index must be rebuilt each night by re-sorting the contents of the database.
AT&T has hired you as a consultant to analyze their computing needs for the nightly sorting run. After carefully checking GitHub, you have found three sorting algorithms – A, B, and C – that can sort n phone numbers in 4 × 10−6n2, 10−4nlog2 n, and 1.4 × 10−4n seconds respectively on a single processor.
11. What is the smallest problem size n0 such that algorithm B is strictly faster than algorithm A for all n ≥ n0? (Hint: Plugging in values for n or using Newton’s method are acceptable ways to solve the problem, and you are welcome to use online tools such as Wolfram Alpha and Desmos.) Explain your reasoning.
12. What is the smallest problem size n1 for which algorithm C is strictly faster than algorithm B for all n ≥ n1? Explain your reasoning.
13. Describe how to construct a sorting algorithm that always achieves the best running time of any ofalgorithms A, B, or C for a given n.