• Graded Problems
1. Whatis isthethetightworstupper-caseboundruntimetotheworstperformance-caseruntimeof performancetheprocedureofthebelow?procedure below?
c = 0
i = n
while i > 1 do
for j = 1 to i do
c = c + 1
end for
i = oor(i=2)
end while
return c
2. Arrange these functions under the O notation using only = (equivalent) or (strict subset of):
(a) 2log n
(b) 23n
(c) nn log n
(d) log n
(e) n log n2
(f) nn2
(g) log(log(nn))
E.g. for the function n, n + 1, n2, the answer should be
O(n + 1) = O(n) O(n2):
1
3. Given functions f1; f2; g1; g2 such that f1(n) = O(g1(n)) and f2(n) = O(g2(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample.
(a) f1(n) f2(n) = O (g1(n) g2(n))
(b) f1(n) + f2(n) = O (max (g1(n); g2(n)))
(c) f1(n)2 = O g1(n)2
(d) log2 f1(n) = O (log2 g1(n))
4. Given an undirected graph G with n nodes and m edges, design an O(m+ n) algorithm to detect whether G contains a cycle. Your algorithm should output a cycle if G contains one.
• Practice Problems
1. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
2. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
2
