COMP 3270 Introduction to Algorithms
Homework 2
2. (30 pts) Use the Master Method to solve the following three recurrence relations and state the
complexity orders of the corresponding recursive algorithms.
(a) 𝑇ሺ𝑛ሻ ൌ 2𝑇ሺ99𝑛/100ሻ 100𝑛
(b) 𝑇ሺ𝑛ሻ ൌ 16𝑇ሺ𝑛/2ሻ 𝑛ଷ𝑙𝑔𝑛
(c) 𝑇ሺ𝑛ሻ ൌ 16𝑇ሺ𝑛/4ሻ 𝑛ଶ
3. (50 pts) Use the Substitution Method to solve the following recurrence relation. Give an exact solution:
𝑇ሺ𝑛ሻ ൌ 𝑇ሺ𝑛െ1ሻ 𝑛/2
1.. (20pts) Compare the following pairs of functions in terms of order of magnitude. In each case, say
whether 𝑓ሺ𝑛ሻ ൌ Ο൫𝑔ሺ𝑛ሻ൯, 𝑓ሺ𝑛ሻ ൌ Θ൫𝑔ሺ𝑛ሻ൯, or 𝑓ሺ𝑛ሻ ൌ Ω൫𝑔ሺ𝑛ሻ൯.
𝑓ሺ𝑛ሻ 𝑔ሺ𝑛ሻ
a. 100𝑛 𝑙𝑜𝑔 𝑛 𝑛 ሺ𝑙𝑜𝑔 𝑛ሻଶ
b. 𝑙𝑜𝑔 𝑛 𝑙𝑜𝑔ሺ𝑛ଶሻ
c.
𝑛ଶ
𝑙𝑜𝑔 𝑛
𝑛ሺ𝑙𝑜𝑔 𝑛ሻଶ
d. 𝑛
ଵ
ଶ 𝑙𝑜𝑔 𝑛ହ
e. 𝑛2 3
