CSCI 570 HW 2 Solution

• 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

1. Arrange these functions under the O notation using only = (equivalent) or (strict subset of):

1. ₂log n

1. 2³ⁿ
2. _nn log n

1. log n
2. n log n²

1. nⁿ²

1. log(log(nⁿ))

E.g. for the function n, n + 1, n², the answer should be

O(n + 1) = O(n) O(n²):

1

1. Given functions f₁; f₂; g₁; g₂ such that f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)). For each of the following statements, decide whether you think it is true or false and give a proof or counterexample.

1. f₁(n) f₂(n) = O (g₁(n) g₂(n))

1. f₁(n) + f₂(n) = O (max (g₁(n); g₂(n)))
2. f₁(n)² = O g₁(n)²

1. log₂ f₁(n) = O (log₂ g₁(n))

1. 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.

1. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.