EL9343 Homework 2 Solved

Description

EL9343 Homework 2

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.