SEM-5 Analysis and Design of Algorithms (ADA) Assignments

1. Arrange following rate of growth in increasing order.
     2n, nlgn, n2, 1, n, lgn, n!, n3, nn, n!, √𝑛

        1 < lgn < √ N < N < N log N < n2 < n3 < 2n < n! < nⁿ

2. Prove that T(n) = n3 + 20n is Ω(n2)

3. Prove that T(n) = n 3 + 20n + 1 is not O(n2 )

4. Let f(n) and g(n) be asymptotically positive functions. Prove the following. f(n) + g(n) = Θ(max(f(n), g(n))).

5. Prove that (n + a)b = Ө(nb)

6. Is 2n+1 = Ο(2n) ? Explain

7. Is 22n = Ο(2n) ? Explain.

8. Prove that (lgn)lgn = Ω(n3/2)

9. Prove that lg(n!) = Ө(nlgn)