Design and Analysis of Algorithms

720 Design and Analysis of Algorithms

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:

n

n

n

2

log(n)

3

n

n

n 2

n

log

10

(n) nlog(n)

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:

n

5

/ 100, 5, (log

2

n)

2

, n

2

/ (1 + n), 2

2 log

2

n

, n

2

log ...