Analysis of Algorithms : An Active Learning Approach

1.5 DIVIDE AND CONQUER ALGORITHMS 31

This means that L, the minimum depth of the decision tree for sorting

problems, is of order O(N lg N). We now know that any sort that is of order

O(N lg N) is the best we will be able to do, and it can be considered optimal.

We also know that any sort algorithm that runs faster than O(N lg N) must not

work.

This analysis for the lower bound for a sorting algorithm assumed that it

does its work through the comparison of pairs of values from the list. In

Chapter 3, we will see a sorting algorithm (radix sort) that will run in linear

time. That algorithm doesn’t compare key values but rather separates them

into “buckets” to accomplish its work.

1.5.3

1. Fibonacci numbers can be calculated with the algorithm that follows. What
   is the recurrence relation for the number of “additions” done by this algo-
   rithm? Be sure to clearly indicate in your answer what you think the direct
   solution, division of the input, and combination of the solutions are.
   int Fibonacci( N )
   N the Nth Fibonacci number should be returned
   if (N = 1) or (N = 2) then
   return 1
   else
   return Fibonacci( N-1 ) + Fibonacci( N-2 )
   end if


2. The greatest common divisor (GCD) of two integers M and N is the largest
   integer that divides evenly into both M and N. For example, the GCD of 9
   and 15 is 3, and the GCD of 51 and 34 is 17. The following algorithm will
   calculate the greatest common divisor of two numbers:
   GCD(M, N)
   M, N are the two integers of interest
   GCD returns the integer greatest common divisor
   if ( M < N ) then
   swap M and N
   end if
   if ( N = 0) then
   return M
   else
   quotient = M / N //NOTE: integer division

■1.5.3 EXERCISES