Analysis of Algorithms : An Active Learning Approach

32 ANALYSIS BASICS

remainder = M mod N

return GCD( N, remainder )

end if

Give the recurrence relation for the number of multiplications (in this case,

the division and mod) that are done in this function.

3. We have a problem that can be solved by a direct (nonrecursive) algorithm
   that operates in N^2 time. We also have a recursive algorithm for this prob-
   lem that takes N lg N operations to divide the input into two equal pieces
   and lg N operations to combine the two solutions together. Show whether
   the direct or recursive version is more efficient.


4. Draw the tournament tree for the following values: 13, 1, 7, 3, 9, 5, 2, 11,
   10, 8, 6, 4, 12. What values would be looked at in stage 2 of finding the
   second largest value in the list?


5. What is the lower bound on the number of comparisons needed to do a
   search through a list with N elements? Think about what the decision tree
   might look like for this problem in developing your answer. (Hint: The
   nodes would be labeled with the location where the key is found.) If you
   packed nodes into this tree as tightly as possible, what does that tell you
   about the number of comparisons needed to search?

1.6 RECURRENCE RELATIONS

Recurrence relations can be directly derived from a recursive algorithm, but

they are in a form that does not allow us to quickly determine how efficient

the algorithm is. To do that we need to convert the set of recursive equations

into what is called closed form by removing the recursive nature of the equa-

tions. This is done by a series of repeated substitutions until we can see the

pattern that develops. The easiest way to see this process is by a series of exam-

ples.

A recurrence relation can be expressed in two ways. The first is used if there

are just a few simple cases for the formula:

Tn()= 2 Tn()– 2 – 15

T() 2 = 40

T() 1 = 40