The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, Timothy Horscroft, and Hanna Kurniawati
Exercise 1 Math Refresher
1. Calculate lim 6n n→∞ 2n
2. Calculate lim an (where a > b) n→∞ bn
Semester 2, 2020 Tutorial 1
3. Calculate lim
n2+en n→∞ 2n+e4n
4. Please compute the sum of the first consecutive n odd numbers
5. The cost of building the first level of an apartment building is 5U, and each subsequent level is more expensive by 2U. How much is the total cost for building an apartment with l levels? Please specify your answer in terms of l and U.
Exercise 2 Time Complexity
Please derive the worst case total time required by the following algorithms, assuming they are executed in a RAM computational model. Please represent your total time in terms of the size of the input array (i.e., A.length). This total time is similar to the notation T(n) in https://cs.anu.edu.au/courses/ comp3600/week1-introduction-aftClass.pdf.
Algorithm 1 BubbleSort(An array of integers A)
1: 2: 3: 4:
fori=1toA.lengthdo
for j = A.length downto i + 1 do
if A[j] < A[j − 1] then Swap A[j] and A[j − 1]
Algorithm 2 BinarySearch(A sorted array of integers A, An integer v)
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11:
Lets=1
Let e = A.length
whiles≤edo m = s+e
2
if A[m] == v then Return m
else if A[m] < v then Let s = m + 1
else
Let e = m − 1 Return unsuccessful.
1
Exercise 3 Estimation
Estimate an upper bound on the input size required for a modern computer (under the RAM model) to run an algorithm in 1 second. Assume modern computers execute one hundred million operations per second (you may assume a constant factor for each of the complexities e.g. O(nlogn) means exactly n log n operations are required).
time complexity O(1)
O(log n)
O(√n)
O(n)
O(n log n) O(n2) O(n3) O(2n)
O(n!)
input size
n ≤ 108
Properties of big O
1. Suppose f1(n) = O(g1(n)) and f2(n) = O(g2(n)). Is it true that f1(n) + f2(n) = O(g1(n) + g2(n))?
Please provide a proof or counter example.
2. Suppose f1(n) = O(g1(n)) and f2(n) = O(g2(n)). Is it true that f1(n) · f2(n) = O(g1(n) · g2(n))? Please provide a proof or counter example.
Exercise 4
2