CSCI 570 - Fall 2021 - HW 2Due September 9th1 Graded Problems1. What is the worst-case runtime performance of the procedure below?c = 0i = nwhile i > 1 dofor j = 1 to i doc = c + 1end fori = floor(i/2)end whilereturn c2. 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 logn2(f) nn2(g) log(log(nn))E.g. for the function n, n + 1, n2, the answer should beO(n + 1) = O(n) ⊂ O(n2).13. Given functions f1, f2, g1, g2such that f1(n) = O(g1(n)) and f2(n) =O(g2(n)). For each of the following statements, decide whether you thinkit 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= Og1(n)2(d) log2f1(n) = O (log2g1(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 shouldoutput a cycle if G contains one.2 Practice Problems1. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.2. Solve Kleinberg and Tardos, Chapter 3, Exercise
View Full Document
Unlocking...