Analysis of Algorithm

Analysis of Algorithms Homework 1

Problem 1.

Some functions are given below. Sort them in ascending order of asymptotic growth (big-O). (lg is log function with base 2)

1. 5lgn 2. 6nlgn 3. nn/8 4. lglgn 5. n0.5 6. 2nlgn 7. lg11n 8. (n/2)n 9. n0.5lgn 10. 3n

Problem 2.

Solve the recurrence relations using Master method

a) T(n) = 2T(n/2) + 3n b) T(n) = 2T(n/2) + 4n0.5 c) T(n) = 2T(n/2) + 2n2 d) T(n) = 2T(n/2) + 3nlgn e) T(n) = 2T(n/2) + θ(n)

Problem 3. Calculate the running time of the algorithms using big-oh notation:

a) for (i = 1; i*i<n; i++) printf(“%d\n”, i**2)

b) for (i = n; i > 1; i = ceil(i/2)) printf(“%f\n”, i);