Design and Analysis of Algorithms: Assignment-II

1. Discuss the importance of "Asymptotic Notations" used by computer professionals.

Explanation of each notation: 1m
Definition of each notation: 2m
Figure showing the order of growth: 2m
Minimum 2 examples: 1m
Total=6 marks x 3 Notations=18 Marks.


2. Write short note on "little-oh notation" (1+1+1=3m)

3. Write the 'General Plan to find time efficiencies' for non-recursive algorithms with example. (5m)

4. Write pesudocode and find the time efficiency of following algorithms. (5 x 10m=50 marks)
    
    To find largest element in a list of n numbers.

     Pseudocode=3m
     Five Steps to find Time Efficiency= 5m
     Total=10m.

    Element Uniqueness Problem.
    Product of 2 matrices A and B. (Matrix Multiplication)
    To find the number of binary digits in a binary representation of decimal number.

5. Prove the following  THEOREM (5m)

    If t1(n) = O(g1(n)) and t2(n) = O(g2(n)) then
        t1(n)+t2(n) = O(max{g1(n),g2(n))