EL9343 Homework 1

Description

1. Prove the Transpose Symmetry property, i.e. f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
2. Problem 3-1 in CLRS Text book.
3. Problem 3-2 in CLRS Text book.
4. You have 5 algorithms, A1 took 𝑂(𝑛) steps, A2 took Θ(𝑛 log 𝑛 ) steps, and A3 took Ω(𝑛) steps, A4 took
𝑂(𝑛 steps, A5 took steps. You had been given the exact running time of each algorithm, but 3
) 𝑜(𝑛
2
)
unfortunately you lost the record. In your messy desk you found the following formulas:
(a) 3𝑛𝑙𝑜𝑔
2
𝑛 + 𝑙𝑜𝑔
2
𝑙𝑜𝑔
2
𝑛
(b) 3(2
2𝑙𝑜𝑔
2
𝑛
) + 5𝑛 + 1234567
(c)
2
𝑙𝑜𝑔
4
𝑛
3 + 𝑛 + 9
(d) (𝑙𝑜𝑔
2
𝑛)
2
+ 5
(e) 3𝑛!
(f) 2
3𝑙𝑜𝑔
2
𝑛
(g) 2
2𝑙𝑜𝑔
2
𝑛
For each algorithm write down all the possible formulas that could be associated with it.
5. For the following algorithm: Show what is printed by the following algorithm when called with
MAXIMUM(A, 1, 5) where A = [10, 8, 6, 4, 2]? Where the function PRINT simple prints its arguments in
some appropriate manner.