Design and Analysis of Algorithms

Appendix E

Additional Exercises with Solutions

In this appendix we give additional exercise with their solutions.

E.1 ADDITIONAL EXERCISES

E.1.1 Chapter 4: Loop Design Issues

1. Arrange the following functions of n in their correct order, using the idea of Order notation, giving the reasons:
   
2. Derive the asymptotic time complexity of the following algorithm:

   Algorithm E.1.1: print_n()

   1	if n is non-zero then
   2	print the value (n/10) using print_n;
   3	print the digit (n mod 10);
   4	end

3. Here is a list of functions of one variable n:

   Place them in a list from left to right, so that if f(n) is any function in the list and g(