Complexity and ThreeSum
Assignment 3
Submit your answers via Moodle. Submissions may be uploaded as PDF or as plain text files.
A LaTeX answer template is available here: answers.tex.
New to LaTeX? See the LaTeX guide for DSA students.
Exercise 1: Complexity groups (12 points)
Group the following functions and sort these groups by complexity in ascending order.
Two functions fi and fj are in the same group iff
fi in O(fj) and fj in O(fi).
f1(n) = 7 log n + n7 |
f2(n) = log log n + log n |
f3(n) = 2256 + n2 + log n |
f4(n) = 211 + 17 |
f5(n) = 13 log log n - 5 |
f6(n) = n5 + 2n-5 + 2n log n |
f7(n) = n + 3n log n |
f8(n) = 5(n - 3) + 20 |
f9(n) = n2(12n3 - log n + 7n5) |
f10(n) = 3 log n + 1 |
f11(n) = n log n + 66 log n |
f12(n) = n2 - n - 1 |
Exercise 2: Fast ThreeSum (20 points)
Implement the N^2 log N algorithm for 3-Sum presented in the lecture (slide 62).
Use the Stopwatch class to estimate the time for the provided
2Kints.txt, 4Kints.txt, and 8Kints.txt,
and compare the binary-search solution to the brute-force solution.
You can find the 3-Sum algorithm and the binary-search implementation in the slides. The input files for this exercise are available here: Material.zip. Please submit your measured times and source code via Moodle.
Exercise 3: Fibonacci, iterative vs. recursive (10 points)
Determine the worst-case, average-case, and best-case runtime complexity of both algorithms using tilde notation.
def fibIter(n):
if n <= 0:
return 0
if n == 1:
return 1
a = 0
b = 1
i = 2
while i <= n:
aa = b
bb = a + b
a = aa
b = bb
i += 1
return b
def fibRek(a):
if a == 1 or a == 2:
return 1
else:
return fibRek(a - 1) + fibRek(a - 2)