CSE 310 Recitation 2
Name -
Section – Dr. Richa (M/W/Th/F) (Circle one)
ASU ID -
Instruction
1. Asymptotic upper bound ( ), Asymptotic lower bound ( ), and Asymptotically tight Big-O Big-Ω
bound Big-Θ
2. Bubble sort algorithm
Recitation Exercise Quiz
1. Determine and for the following equations.Big-O, Big-Ω, Big-Θ
a. 2n + log n
O(n), Ω(n), Θ(n)
b. n + 3n + 4n + 5
3 2
O(n ), Ω(n
3 3), Θ(n3)
2 + 1000n + log n
c. n 3 10
O(2 ), Ω(2 ), Θ(2 )
n n n
2. What is the worst-case time complexity of the bubble sort algorithm given items ? (use the n
Big-O notation)
# of iterations in the inner loop :
→ O(n )
2
1
3. Sort the following upper-bounds in decreasing order.
O(n!), O(n), O(log n), O(n ), O(2 ), O(1), O(n log n)
2 n
O(n!), O(2 ), O(n ), O(n log n), O(n), O(log n), O(1),
n 2
2
