Solved CSCI570 Homework 2 1. Arrange these functions under the Big-𝒪 notation in increasing order of growth rate

Description

FALL 2025

1. Arrange these functions under the Big-𝒪 notation in increasing order of growth rate, with
𝑔(𝑛) following 𝑓(𝑛) in your list if and only if 𝑓(𝑛) = 𝒪(𝑔(𝑛)); mention equality (of
growth-rate) if 𝑓(𝑛) = 𝒪(𝑔(𝑛)) and also 𝑔(𝑛) = 𝒪(𝑓(𝑛)). Here, log(𝑥) = log!(𝑥), i.e.,
denotes the logarithm with base 2):
2″#$(&)
, log(𝑛) , log(𝑛!), 𝑛 log(𝑛!), log(log(𝑛&)), 4(&, 𝑛& “#$(&)
, 𝑛&!
, 3)&
(10 points)
2. For each of the following, indicate whether 𝑓(𝑛) ∈ 𝒪(𝑔(𝑛)), 𝑓(𝑛) ∈ Θ(𝑔(𝑛)), or 𝑓(𝑛) ∈
Ω(𝑔(𝑛)). Here, log(𝑥) = log!(𝑥), i.e., denotes the logarithm with base 2. (10 points)
(a) 𝑓(𝑛) = 𝑛! and 𝑔(𝑛) = 2!”
(b) 𝑓(𝑛) = 𝑒& and 𝑔(𝑛) = 𝑛”#$ &
(c) 𝑓(𝑛) = 2& and 𝑔(𝑛) = 2(&
(d) 𝑓(𝑛) = 𝑛! and 𝑔(𝑛) = 2*”#$ &
(e) 𝑓(𝑛) = log 𝑛 and 𝑔(𝑛) = log(log(6!&))
3. We have a connected graph 𝐺 = (𝑉, 𝐸), and a specific vertex 𝑢 ∈ 𝑉. Suppose we compute a
DFS tree rooted at 𝑢, and obtain a tree 𝑇 (remember that a DFS tree includes all nodes of 𝐺).
Suppose we then compute a BFS tree rooted at 𝑢, and obtain the same tree 𝑇. Prove by
contradiction that 𝐺 is the same as 𝑇, that is, 𝐺 cannot contain any edges that do not belong
to 𝑇. (10 points)
Hint: For any edge (𝑥, 𝑦) in 𝐺, how much can the level of 𝑥 in the BFS T differ from the
level of 𝑦 in it? Further, what can we say about the locations of 𝑥 and 𝑦 relative to each other
in the DFS T?
4. Given an unweighted and undirected graph 𝐺 = (𝑉, 𝐸) and an edge 𝑒 ∈ 𝐸. Design an
algorithm to determine whether the graph 𝐺 has a cycle containing that specific edge 𝑒. Also,
determine the time complexity of your algorithm with explanation. Note: To be eligible for
full credits on this problem, the running time of your algorithm should be bounded by
𝒪(|𝑉| + |𝐸|). (10 points)
Ungraded Problems:
1. Given functions 𝑓+, 𝑓!, 𝑔+, 𝑔! such that 𝑓+(𝑛) = 𝒪(𝑔+(𝑛)) and 𝑓!(𝑛) = 𝒪(𝑔!(𝑛)). For each
of the following statements, decide whether you think it is true or false, and give a proof or
counterexample. (12 points)
(a) 𝑓+(𝑛) + 𝑓!(𝑛) = 𝒪(max(𝑔+(𝑛), 𝑔!(𝑛)))
(b) 𝑓+(𝑛) ⋅ 𝑓!(𝑛) = 𝒪(𝑔+(𝑛) + 𝑔!(𝑛))
(c) 𝑓+(𝑛)! = 𝒪(𝑔+(𝑛)!)
(d) log 𝑓+(𝑛) = 𝒪(log(𝑔+(𝑛)))
2. Consider the following prime filtering algorithm that outputs all the prime numbers in 2, … , 𝑛
(the pseudo code is presented in Algorithm 1). (10 points)
(a) Please prove this algorithm is correct (that is, a positive integer 𝑘 that 2 ≤ 𝑘 ≤ 𝑛 is a
prime if and only if isPrime(𝑘) = True). (5 points)
(b) Please calculate the time complexity under the Big-𝒪 notation. (5 points)
3. A directed graph 𝐺 = (𝑉, 𝐸) is singly connected if 𝐺 contains at most one simple path from 𝑢
to 𝑣 for all vertices 𝑢, 𝑣 ∈ 𝑉 . Construct an algorithm using DFS to determine whether or not a
directed graph is singly connected. Also, determine the time complexity of your algorithm and
justify your answer. (10 points)