The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, and Hanna Kurniawati
Exercise 1 Complexity Classes
1. Briefly explain your answer to the following questions.
Semester 2, 2020 Tutorial 2
• If I prove that an algorithm takes O(n2) worst-case-time, is it possible that it takes O(n) on all inputs?
• If I prove that an algorithm takes θ(n2) worst-case-time, is it possible that it takes O(n) on some inputs?
2. True or False?
• Is 2n+1 = O(2n)?
• Is 22n = O(2n)?
• Islogn=o(nε)forallε>0?
• Isn=Ω(n)?
• Islogn=O(n−1)?
• Islog3n =Θ(log2n)
• There exists a function f(n) which is in both O(g(n)) and ω(g(n))
• There exists a function f(n) which is in both Θ(g(n)) and o(g(n))
• If f(n) = θ(g(n)) then limn→∞ f(n) = C
Exercise 2
1. Use induction to prove n i=1
2. Use induction to prove n
Exercise 3
2
g(n)
Math Refresher: Proof by Induction
i = n(n+1) 2
= n n+1
Algorithm 1 BubbleSort(An array of integers A) 1. 1: fori=1toA.lengthdo
1 i=1 i(i+1)
Correctness
2: 3: 4:
2.
for j = A.length downto i + 1 do if A[j]