COMP 582 GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS Spring 2023 Homework #1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework #1
COMP 582
GRADUATE DESIGN AND ANALYSIS OF ALGORITHMS
Spring 2023
Problem 1
For each statement below explain if it is true or false and prove your answer. Be as precise as you can. The base of log is 2 unless stated otherwise.
1. ^n = Θ(2log n2 )
2. 3nlog n + n = O(
)
3. Let f and g be positive functions. If f(n) + g(n) = Ω(f(n)) then g(n) = O((f(n))2 ).
Problem 2
1. Prove that
2. Prove by induction that 之
= 
for all n ≥ 1.
Problem 3
Resolve the following recurrences. Use Master theorem, if applicable. In all ex- amples, assume that T(1) = 1. To simplify your analysis, you can assume that n = ak for some a,k.
1. T(n) = 8T(n/4) + n
2. T(n) = 8T(n/2) + n3
3. T(n) = T(n/2) + logn
4. T(n) = 10T(n/10) + n
2023-02-16