Introduction to Algorithms  Homework 2

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௡