CS2230 Computer Science II: Data Structures Lab
Asymptotic Analysis
The purpose of this lab is to give you practice for HW4. All of the problems will be of the same type as those on the homework. Practice for Part 1 and Part 2 are here. Practice for Part 3 on analyzing the running time of algorithms will be next week.
Goals for this prelab
• Use Big-Oh/Theta/Omega notation Part 1: Growth rate
1. Order the following functions by asymptotic order of growth (lowest to highest)
Part 2: Proof and Analysis
6𝑛+9 7𝑛𝑙𝑜𝑔𝑛
800𝑛 6 ∗ 𝑛6
22𝑛 log2 𝑛
2. For the function below, find 𝑔(𝑛) such that 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛)). Provide brief justification for your answer by finding a suitable c and n0.
𝑓(𝑛)= 15𝑛16+ 3𝑛log𝑛+ 2𝑛
3. For the function below, find 𝑔(𝑛) such that 𝑓(𝑛) ∈ Ω(𝑔(𝑛)). Provide brief justification
for your answer by finding a suitable c and n0.
𝑓(𝑛)= 15𝑛16+ 3𝑛log𝑛+ 2𝑛
4. For each of the expressions below, find an 𝑓(𝑛) such that the expression is in Θ(𝑓(𝑛)) (i.e., big-Theta notation). Provide brief justification for your answer (in terms of finding
a c’, c’’, and n0).
𝑓(𝑛)= 15𝑛16+ 3𝑛log𝑛+ 2𝑛
5. Show that the following statement is true:
2𝑛+5 ∈ 𝑂(2𝑛)