Homework 2, CPSC 4100 – 01

Description

1) Determine T(n) in terms of a Big-O notation for the following cases. Use expansion method:
a. 𝑇(𝑛) = 𝑇(𝑛 − 2) + 𝑏𝑛 + 𝑐
𝑇(1) = 𝑑
where b, c, and d are constants.
b. 𝑇(𝑛) = 2𝑇(𝑛 − 1) + 1
𝑇(0) = 0
20 points
2) Let 𝑓(𝑛) and 𝑔(𝑛) be asymptotically nonnegative functions. Using the basic definition of Θnotation, prove that max(𝑓(𝑛), 𝑔(𝑛)) = Θ(𝑓(𝑛) + 𝑔(𝑛)). [CLRS 3.1-1]
20 points
3) Prove that 𝑜(𝑔(𝑛)) ∩ 𝜔(𝑔(𝑛)) is the empty set. [CLRS 3.1-7]
10 points