ECS 20 Discrete Math: Discussion 7
Solving recurrence relations with repeated substitutions
1. Solve 𝑇(𝑛) = 2𝑇 (𝑛3) + 𝑛 to within a Θ(∙) result.
Substituting in 𝑛 for 𝑛 in the equation, we have 𝑇 (𝑛) = 2𝑇 ( 𝑛 ) + 𝑛
From the original equation:
𝑇 ( 𝑛 ) = 2 𝑇 ( 𝑛3 ) + 𝑛
𝑇(𝑛) = 2 [2𝑇 ( 𝑛 ) + 𝑛] + 𝑛 32 3
𝑇(𝑛) = 22𝑇 ( 𝑛 ) + 𝑛 (1 + 2) 32 3
Substituting in 𝑛 for 𝑛 in the equation, we have 𝑇 ( 𝑛 ) = 2𝑇 ( 𝑛 ) + 𝑛
32
𝑇(𝑛)=22[2𝑇(𝑛)+ 𝑛]+𝑛(1+2) 3332 3
3𝑛222 𝑇(𝑛)=2 𝑇(33)+𝑛(1+3+(3) )
𝑘𝑛 222 2𝑘−1 𝑇(𝑛)=2 𝑇(3𝑘)+𝑛(1+3+(3) +⋯+(3) )
The series 1 + 2 + (2)2 + ⋯ is a geometric series (where 𝑟 < 1). 𝑠 = 1 3 3 1−𝑟
For left term, use 𝑘 = log3 𝑛:
Mon 11/18/2013
2log3 𝑛𝑇 ( 𝑛 3log3 𝑛
) = 2log3 𝑛𝑇(1)
3 3323
For a small enough 𝑛, 𝑇(𝑛) has constant runtime Θ(1), so we can ignore 𝑇(1). 2log3 𝑛 = (3log32)log3 𝑛 = (3log3 𝑛)log32 = 𝑛log32
Comparing the two terms,Θ(𝑛log32) < Θ(n), therefore 𝑻(𝒏) = 𝚯(𝒏). 2. Solve 𝑇(𝑛) = 3𝑇 (𝑛2) + 𝑛 to within a Θ(∙) result.
𝑇(𝑛) = 3 [3𝑇 ( 𝑛 ) + 𝑛] + 𝑛 22 2
𝑇(𝑛) = 32𝑇 ( 𝑛 ) + 𝑛 (1 + 3) 22 2
3𝑛332 𝑇(𝑛)=3 𝑇(23)+𝑛(1+2+(2) )
𝑘𝑛 332 3𝑘−1 𝑇(𝑛)=3 𝑇(2𝑘)+𝑛(1+2+(2) +⋯+(2) )
Nowconsidertheseries𝑆=1+𝑥+𝑥2 +⋯+𝑥𝑘−1 +𝑥𝑘: 𝑆𝑥 = 𝑥 + 𝑥2 + ⋯ + 𝑥𝑘−1 + 𝑥𝑘 + 𝑥𝑘+1
1 + 𝑆𝑥 = 1 + 𝑥 + 𝑥2 + ⋯ + 𝑥𝑘−1 + 𝑥𝑘 + 𝑥𝑘+1
1 + 𝑆𝑥 = 𝑆 + 𝑥𝑘+1
𝑆𝑥 − 𝑆 = 𝑥𝑘+1 − 1 𝑆(𝑥 − 1) = 𝑥𝑘+1 − 1 𝑆 = 𝑥𝑘+1 − 1
𝑥−1
32 3332
= 1 1−23
= 3. So right term is Θ(n).
1
ECS 20 Discrete Math: Discussion 7
Mon 11/18/2013
3𝑘
332 3𝑘−12−13𝑘
𝑛(1+2+(2) +⋯+(2) )= 1 =2((2) −1) 2
𝑘𝑛3𝑘 𝑇(𝑛)=3 𝑇(2𝑘)+2𝑛((2) −1)
Use 𝑘 = lg 𝑛:
lg𝑛 3 lg𝑛 ) + Θ (2𝑛 (2)
𝑇(𝑛) = 3 Θ(𝑇(𝑛)) = Θ(3
− 1)
− 1)
lg𝑛 𝑛 3 lg𝑛 𝑇 (2lg 𝑛) + 2𝑛 ((2)
lg3 lg𝑛 3lg𝑛 Θ(𝑇(𝑛))=Θ((2 ) )+Θ(2𝑛(2lg𝑛)−2𝑛)
Θ(𝑇(𝑛))=Θ(𝑛lg3)+Θ(2∗3lg𝑛 −2𝑛)=Θ(𝑛lg3)+Θ(𝑛lg3)=𝚯(𝒏𝐥𝐠𝟑)
Solving recurrence relations with recursion trees
Solve 𝑇(𝑛) = 2𝑇 (𝑛2) + 𝑛 to within a Θ(∙) result. Solve 𝑇(𝑛) = 𝑇 (𝑛2) + 𝑇 (𝑛3) + 𝑛 to within a Θ(∙) result.
To determine the height, consider the number of recursions to get to 𝑇(1), at which point the recursion stops. For 𝑇(𝑛) = 2𝑇 (𝑛2) + 𝑛, the height is lg 𝑛 since 𝑛 is being divided by two each time. There are lg 𝑛 levels each
taking 𝑛 time, so it is Θ(𝑛 lg 𝑛).
For 𝑇(𝑛) = 𝑇 (𝑛2) + 𝑇 (𝑛3) + 𝑛 we do not need to consider the height, because we see that the total runtime is 𝑛
times a constant number. Its runtime is capped at 6n, so it is Θ(𝑛). 2
ECS 20 Discrete Math: Discussion 7 Mon 11/18/2013 Big-O and Theta
𝑂(∙) is an upper bound. Θ(∙) is both an upper and lower bound (or tight bound). True or false? Note: > is not defined. Θ(𝑓) > Θ(𝑔) has been re-written to 𝑔 ∈ 𝑂(𝑓).
e) 𝑛2 =𝑂(𝑛)F
f) 𝑛2 =Θ(𝑛)F
g) 100n∈𝑂(0.01𝑛2)T
a) 𝑛=𝑂(𝑛)T b) 𝑛=Θ(𝑛)T c) 𝑛=𝑂(𝑛2)T d) 𝑛=Θ(𝑛2)F
For k) and l), since log𝑏 𝑥 = log𝑑 𝑥 / log𝑑 𝑏, different logarithmic bases only differ by a multiplicative constant. So Θ(lg 𝑛) = Θ(ln 𝑛) = Θ(log 𝑛). Alternatively lg 𝑛 , ln 𝑛, log 𝑛 ∈ O(lg 𝑛).
Rank the following functions by order of growth: 1, 𝑛, 𝑛2, 𝑛3, lg𝑛, ln𝑛, lglg𝑛, lnln𝑛, 2𝑛, 𝑛lg𝑛, 𝑛lg𝑛
1 lnln𝑛 lglg𝑛 ln𝑛 lg𝑛
𝑛
𝑛lg𝑛
𝑛2
𝑛3 𝑛lg𝑛
2𝑛
h) 2n ∈𝑂(2√𝑛)>F For h), Θ(2√𝑛) and Θ(2𝑛) do have two different growth rates.
i) nlg𝑛 ∈𝑂(2𝑛)T j) 𝑛!∈𝑂(2𝑛)F
k) ln𝑛∈𝑂(lg𝑛)T l) log𝑛∈𝑂(ln𝑛)T
3