1.5 DIVIDE AND CONQUER ALGORITHMS 27

Now that we have this generic formula, the answer to the question posed at
the start of the last paragraph is quite easy. All we need to do is to plug in the
complexities for each piece given into the previous general equation. This
gives the following result:

or a bit more simply, because all smaller sets are the same size,

This form of equation is called a recurrence relation because the value of
the function is based on itself. We prefer to have our equations in a form that
is dependent only on N and not other function calls. The process that is used
to remove the recursion in this equation will be covered in Section 1.6, which
covers recurrence relations.
Let’s return to our factorial example. We identified all of the elements in
the factorial algorithm relative to the generic DivideAndConquer. We now
use that identification to decide what values get put into the general equation
above. For the Factorial function, we said that the direct solution does no
calculations, the input division and result combination steps do one calculation
each, and the recursive call works with a problem size that is one smaller than
the original. This results in the following recurrence relation for the number
of calculations in the Factorial function:

■ 1.5.1 Tournament Method
The tournament method is based on recursion and can be used to solve a
number of different problems where information from a first pass through the
data can help to make later passes more efficient. If we use it to find the largest
value, this method involves building a binary tree with all of the elements in

DAC()N

N^2 forN≤SizeLimit

lgN DAC()N⁄ 4 +N

i=1

8

+∑ forN>SizeLimit















=

DAC()N N

(^2) forN≤SizeLimit
 lgN++8 DAC()N⁄ 4 N forN>SizeLimit



Calc()N^0 for N=^1
 1 Calc++()N–^11 forN>^1

= 