Design and Analysis of Algorithms, 2nd Edition by Pearson

Appendix D

Additional Exercises with Solutions

In this appendix we give additional exercise with their solutions.

D.1   Additional Exercises

D.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 D.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:

    

   n⁵/100, 5, (log ₂ n)², n²/(1 + n), 2^{2 log₂n}, n² log ₂ n, n² + 27n, 2ⁿ

    

   Place them in a ...