EL9343 Homework 2

Description

1. First use the iteration method to solve the recurrence, draw the recursion tree to analyze.
𝑇(𝑛) = 𝑇(
𝑛
2
) + 𝑇(
𝑛
3
) + 𝑛
Then use the substitution method to verify your solution.
2. Use the substitution method to prove that 𝑇(𝑛) = 2𝑇( is .
𝑛
2
) + 𝑐𝑛𝑙𝑜𝑔
2
𝑛 𝑂(𝑛(𝑙𝑜𝑔
2
𝑛)
2
)
3. Solving the recurrence:
𝑇(𝑛) = 3𝑇(
3
𝑛 ) + 𝑙𝑜𝑔
2
𝑛
(Hint: Making change of variable)
4. You have three algorithms to a problem and you do not know their efficiency, but fortunately, you
find the recurrence formulas for each solution, which are shown as follows:
A: 𝑇(𝑛) = 3𝑇(
𝑛
3
) + θ(𝑛)
B: 𝑇(𝑛) = 2𝑇(
9𝑛
10
) + θ(𝑛)
C:𝑇(𝑛) = 3𝑇(
𝑛
3
) + θ(𝑛
2
)
Please give the running time of each algorithm (In θ notation), and which of your algorithms is the
fastest (You probably can do this without a calculator)?
5. Can the master theorem be applied to recurrence of 𝑇(𝑛) = 𝑇( ? Why does it work or 𝑛
2
) + 𝑛
2
𝑙𝑔𝑛
not? Provide the asymptotic upper bound for this recurrence.