CS2230 Computer Science II: Data Structures Homework 4
Asymptotic Analysis
Goals for this assignment
• Practice using Big-Oh/Theta/Omega notation
• Analyze the running times of some algorithms
Submission Checklist You should submit:
• a PDF file titled hw4.pdf containing the answers to the problems in this document
Upload it on ICON under Assignments > Homework 4. Physical paper copies are not accepted. If you handwrite, then your
work must be legible.
The level of justification expected is the same as what is expected from lecture and section.
Part 1:
Experiments
1. Lion and Giraffe are arguing about the solution to your upcoming homework assignment on sorting algorithms. Lion claims that their O(n log n)-time solution must always be faster than Giraffe’s O(n2) solution. However, Giraffe claims that they ran several experiments on both algorithms on their laptop and sometimes theirs was faster. Explain what might have happened.
Growth rate 100 2
a. 2 | 2𝑛 +200𝑛 log 𝑛|𝑛 −2000|𝑛 |3 |250n log 𝑛|300n log 𝑛
Part 2:
2. Order the following functions by growth rate:
b.63 | 2𝑛 |3𝑙𝑜𝑔𝑛 |2 |10 |10
2 2 3 90 𝑛−1 2 3 2 4 𝑛+2 log2 𝑛 log10 𝑛
Part 3:
3. Give a tight big-Oh bound on each of the following. Provide brief justification for your answer (by finding a
Proof and Analysis
suitable c and n0 or taking limits)
a. 3𝑛log 𝑛 +2log 𝑛 22
b.6𝑛2∗3𝑛 −50𝑛
4. Give a tight big-𝚯 bound on each of the following. Provide brief justification for your answer (by finding a c1, c2,
a. 400𝑛5/2 + 3𝑛3
and n0 or taking limits)
b. 33𝑛2 log2 𝑛 + 1000𝑛2
5. Show that the following statements are true:
a. 𝑛2 ∈ Ω(𝑛 𝑙𝑜𝑔 𝑛) b. 100𝑛6𝑙𝑜𝑔𝑛 ∈ 𝑂(𝑛7)
Part 4: Algorithm Analysis
Given the following codes below, give a 𝑓(𝑁) such that 𝑅(𝑁) ∈ 𝑂(𝑓(𝑁)) where R(N) is defined for each problem. For each problem, please provide
i. ii.
iii. 6.
summation
explanation of how the code relates to the summation
a. (loops require discussing iterations and steps per iteration)
b. (recursion requires a diagram)
your f(N)
R(N) is the running time of foo(N)
static int foo(int x) {
for (int i=0; i
break; }
} }
}
7.
R(N, M) is the running time of baz(x, y) when x has length N and y has length M. In this case you are finding an 𝑓(𝑁, 𝑀) such that 𝑅(𝑁, 𝑀) ∈ 𝑂(𝑓(𝑁, 𝑀)) . 𝑓(𝑁, 𝑀) must include both N and M.
static void baz(int[] x, int[] y) { for (int i=0; i