CSE 101 - A LGORITHMS - S UMMER 2000

Lecture Notes 2
Wednesday, July 5, 2000.

Chapter 2

Mathematical Foundations
This chapter presents the fundamental mathematical notions, notations and formulae needed to analyze the running
time of simple algorithms. We assume the reader familiar with well-known properties of logarithms and summations,
such as






loga (b
c) = loga (b) + loga (c),

loga (b=c) = loga (b) , loga (c),
loga (bc ) = c
loga (b),

cloga (b) = bloga (c) ,

n
 1 + x + x +


+ xn = x x ,,1 1 ,
2

+1

as well as with basic concepts of set theory and with simple mathematical reasoning and calculus.
The functions considered in this chapter and most of the rest of the course take natural numbers as arguments.
When not otherwise specified, a function has only one argument and that argument is a natural number.

2.1 Growth of Functions

The order of growth of a running time of an algorithm, as function of input size, gives a simple and usualy appropriate
characterization of the efficiency of an algorithm. We saw that the running time of merge sort was (n log n) while
that of insertion sort was (n2 ), meaning that merge sort is faster than insertion sort on inputs of large enough size. It
is worth noticing that in practice, insertion sort may be more efficient than merge sort on many inputs. In this course,
we only study asymptotic efficiency of algorithms, that is, we are only concerned with how the running time of an
algorithm increases as the size of the input increases toward infinity.
This section introduces some mathematical notation which significantly simplifies the asymptotic analysis of algorithms.

2.1.1

O-Notation

Given a function f , we let

Formally,

O(f (n)) denote the class of functions g for which f is an asymptotically upper bound.

O(f (n)) = fg j (9c > 0)(9n0  0)(8n  n0 ) 0  g(n)  cf (n)g

that is, O(f (n)) is the set of functions g for which there are some constants c > 0 and n0  0 such that g (n) is
positive and smaller than cf (n) for each n larger than n0 . Notice that for each c and n0 as above, one can always
choose any larger c0 and n00 with the same property. In particular, given a finite number of functions g1 ; g2 ; :::; gk in
9

CHAPTER 2. MATHEMATICAL FOUNDATIONS

10

O(f (n)), one can choose a constant c and a number n0 such that gi (n) is positive and smaller than cf (n) for for all
n  n0 and 1  i  k. The following picture shows three functions in O(f (n)):
c f(n)

g (n)
3

g (n)
2

g (n)
1

If the running time T (n) of an algorithm A can be shown to be in O(f (n)) for some function f , then we say that
A is more efficient than any algorithm running in time f (n), even if this may not be true for all the inputs. However,
it is true for inputs of large enough sizes. In fact, it would be more appropriate to say asymptotically more efficient.
Exercise 2.1 Show that 1010 n2 + 2100 n and 10,10 n2 , 2,100 n are in O(n2 ).
Exercise 2.2 Show that n log n 2 O(n2 ).
Exercise 2.3 If g (n)  f (n) for all n  0, then g

2 O(f (n)).
Exercise 2.4 Given g 2 O(f (n)), show that f + g 2 O(f (n)) and that f
g 2 O((f (n)) ).
Exercise 2.5 If g 2 O(f (n)) then O(g (n))  O(f (n)).
Exercise 2.6 Are there any different functions f =
6 g such that g 2 O(f (n)) and f 2 O(g(n))?
Exercise 2.7 If g 2 O(f (n)) and g 2 O(f (n)) then is it the case that g + g 2 O(f (n) + f (n)) and g
g 2
O(f (n)
f (n))? How about g =g 2 O(f (n)=f (n))? How about g g2 2 O(f (n)f2 n )?
Exercise 2.8 Is it the case that for any functions f and g , either g 2 O(f (n)) or f 2 O(g (n))?
Proof: We give a counter-example: let f (n) = 1 + (,1)n and g (n) = 1 , (,1)n for all n  0, so f takes the values
2; 0; 2; 0; 2; 0; ::: and g takes the values 0; 2; 0; 2; 0; 2; :::. For the sake of contradiction, suppose that f 2 O(g(n)).
Then there are c > 0 and n > 0 such that f (n)  cg (n) for all n  n . But that means that f (2k )  cg (2k ) for all
k > n =2, that is, that 2  0. Contradiction. It can be similarly shown that g 62 O(f (n)).
Exercise 2.9 Is it the case that f
g 2 O((f (n)) ) [ O((g (n)) ) for any functions f and g ?
2

1
( )

2.1.2

-Notation

Given a function f , let

(f (n)) denote the set of functions g for which f is an asymptotically lower bound, that is,

(f (n)) = fg j (9c > 0)(9n0  0)(8n  n0 ) 0  cf (n)  g(n)g:

With other words,
(f (n)) is the set of functions g for which there are some constants c > 0 and n0  0 such that
g(n) is bigger than cf (n) for each n larger than n0 . Notice also that for each c and n0 as above, one can always choose

2.1. GROWTH OF FUNCTIONS

11

any larger c0 and n00 with the same property, so given a finite number of functions g1 ; g2 ; :::; gk in O(f (n)), one can
choose a constant c and a number n0 such that gi (n) is bigger than cf (n) for for all n  n0 and 1  i  k . The
following picture shows three functions in
(f (n)):

g (n)
3

g (n)
2

g (n)
1

c f(n)

If the running time of an algorithm A is in O(f (n)) for some function f , then we say that A is less efficient
than an algorithm running in time f (n), even if this may not be true for all the inputs. As before, it is true for inputs of
large enough sizes, so it would be more appropriate to say asymptotically less efficient. The following proposition
shows a natural immediate relationship between the
and the O notations:
Proposition 2.1 Given functions f and g , then g

2
(f (n)) if and only if f 2 O(g(n)).

Proof: Exercise.
Therefore, the
-notation is in some sense inverse to the
without using Proposition 2.1.

O-notation.

Prove the following exercises directly,

Exercise 2.10 Show that the identity function g (n) = n is both in

(log n) and in
((log n)2 ).
Exercise 2.11 Show that 2n is in
(n100 ).

2.1.3

-Notation

We now combine the O and

-notations. Given a function f , let (f (n)) denote the set of functions g for which f is
an asymptotically tight bound, that is,

(f (n)) = fg j (90 < c1 < c2 )(9n0  0)(8n  n0 ) 0  c1 f (n)  g(n)  c2 f (n)g:
Therefore, (f (n)) is the set of functions g for which there are some constants 0 < c1 < c2 and n0  0 such that
g(n) is bigger than c1 f (n) but smaller than c2 f (n) for each n larger than n0 . Notice again that for each c1 ; c2 and n0
as above, one can choose any constants c01 ; c02 with 0 < c01 < c1 < c2 < c02 and any n00 > n0 such that the property
in the definition of the -notation also holds. Hence, given a finite number of functions g1 ; g2 ; :::; gk in (f (n)), one
can choose constants c1 ; c2 and a number n0 such that gi (n) is bigger than c1 f (n) and smaller than c2 f (n) for for all

CHAPTER 2. MATHEMATICAL FOUNDATIONS

12

n  n0 and 1  i  k. The following picture shows two functions in

(f (n)):
c f(n) g (n) g (n)
2

c f(n)
1

Proposition 2.2

(f (n)) = O(f (n)) \

(f (n)) for any function f .

Proof: Exercise.
Exercise 2.12 df e and bf c are in (f (n)) for any function f , where df e and bf c are the functions defined by
df e(n) = df (n)e and bf c(n) = bf (n)c, respectively.
Exercise 2.13 If g 2 (f (n)) then f 2 (g (n)).
Exercise 2.14 If g (n)  f (n) for all n > 0 then (g (n))  O(f (n)) and (f (n)) 
(g (n)).

2.1.4 Some Exercises with Solutions

Exercise 2.15 Is 2n+1 in O(2n )? Is 22n in O(2n )?
Proof: Yes. Take c = 2 and n0 = 1; then, since 2n+1 = 2
2n for all n, we have that for each n  1, 2n+1  c2n .
No. There are no c; n0 such that for each n  n0 , 22n  c2n . To show this, assume there exist such c; n0 . Then
22n = 2n
2n  c
2n , which implies 2n  c. But no constant is bigger than 2n . Contradiction.
Exercise 2.16 Prove that log(n!) 2 (n log n).

Proof: First we prove that log(n!) 2 O(n log n). Since n! = 1
2
3


n , 1
n  n
n


n = nn , we have that
log(n!)  log(nn ) = n log n. Then log(n!) 2 O(n log n).
n=2
Now we prove that log(n!) 2
(n log n). Since n! = 1
2
3


n , 1
n  i=1 n=2 = (n=2)n=2 , where
the  step follows after noticing that the last n=2 product terms of n! are all greater than n=2. Then we have that
log(n!)  log((n=2)n=2 ) = (n log(n=2))=2 = (n log n , n)=2 2
(n log n). Then n log n = O(log(n!)).
Exercise 2.17 Is the function dlog ne! polynomially bounded? Is the function dlog log ne! polynomially bounded?

Proof: The function dlog ne! is not polynomially bounded. The function dlog log ne! is polynomially bounded.
We use the fact that proving that a function f (n) is polynomially bounded is equivalent to proving that log(f (n)) 2
O(log n). To show that this is true, consider that if f is polynomially bounded, then 9c; k; n0 such that 8n  n0 ,
f (n)  cnk , and hence log(f (n))  kc log n, which implies that log(f (n)) 2 O(log n). Similarly, it is possible to
see that if log(f (n)) 2 O(log n) then f is polynomially bounded.
We remind the reader that log(n!) 2 (n log n) and that dlog ne 2 (log n). Then we have that log(dlog ne!) 2
(dlog ne
logdlog ne) = (log n
log log n), so log n
log log n 2 (log(dlog ne!)). Suppose that dlog ne! is

2.1. GROWTH OF FUNCTIONS

13

polynomially bounded, so log(dlog ne!) 2 O(log n). Then log n
log log n 2 O(log n), which is of course false.
Therefore log(dlog ne!) 6= O(log n), and the function dlog ne! is not polynomially bounded. On the other hand, we
have that

log(dlog log ne!) 2 (dlog log ne logdlog log ne)

= (log log n log log log n)
 O((log log n)2 )
 O(log n)
Therefore log(dlog log ne!) 2 O(log n), so the function dlog ne! is polynomially bounded.
Exercise 2.18 Group the following functions by complexity category:
nn + ln n, 5lg n , lg(n!), (lg n)!, pn, en , 8n + 12, 10n + n20 .

n ln n, (lg n)2 , 5n2 + 7n, n5=2 , n!, 4n , nn ,

Proof: Much of the ranking is based on the following facts:

1. Exponential functions grow faster than polynomial functions
than logarithmic functions

lim (lg n) = 0.
n!1 nc

lim n = 0, polynomial functions grow faster

n!1 an

2. The base of a logarithm doesnt matter asymptotically, but the base of an exponential and the degree of a
polynomial do matter.

lim f (n) = c then g(n) 2 (f (n)) if c > 0.

n!1 g(n)
If lim fg((nn)) = 1 then g (n) 2 o(f (n)).
n!1
If lim fg((nn)) = 0 then f (n) 2 o(g (n)).
n!1

3. If

4. LHopitals rule: If f (n) and g (n) are both differentiable with derivatives f 0 (n) and g 0 (n), respectively, and if

nlim
!1 f (n) = nlim
!1 g(n) = 1
then

f (n) = lim f 0 (n)

lim
n!1 g (n) n!1 g 0 (n)

5. If

h f (n) i
f (n)
lim
lg
g(n) = 1 then nlim
n!1
!1 g(n) = 1.

6. Some useful identities:

(a) ( n2 )n=2  n!  nn
p
(b) Stirlings: n!  (n=e)n 2n
ca
(c) logb a = log
logc b
logb n
logb a
(d) a
=n

Then the ordering is the following:

nn and (nn + ln n)
n!
10n + n20
4n

en
(lgn)!

CHAPTER 2. MATHEMATICAL FOUNDATIONS

14

n5=2

5lg n
5n2 + 7n
n log n and log(n!)
8n + 12

n1=2

log2 n
By fact 3,

nn + ln n = lim (1 + ln n ) = 1
lim
n!1 nn
n!1
nn

By facts 3 and 6b,

n p = lim pe = 1
lim n = lim
n!1 n! n!1 (n=e)n 2n n!1 2n

By facts 3 and 6a and by noticing that 10n +n20

10n + n < lim 2(10n) = 0

 2(10n) as n goes to infinity, nlim
n!1 (n=2) n=
!1
n!
20

By fact 3,

10n + n2 0 = lim ( 10 n + n2 0 ) = 1
lim
n!1
n!1 4
4n
4n

By fact 3,

4n = lim 4 n = 1
lim
n!1 en n!1 e

By facts 3, 5, and 6a,

lim e  lim e
= lim n lg e , lg n lg lg n = 1
n!1 (lg n)! n!1 (lg n)lg n n!1
(lg n)! > lim (lg n=2)
lim
5=2
n!1
n!1 5=2

(lg

By facts 6a, 6d, and 3,

n=2)

n)=2

n
= nlim
!1 n1=2 n5=2 = 1
(lg lg

lim n = lim (5=2) lg n , lg 5 lg n  nlim

n!1 5lg n n!1
!1(:18) lg n = 1
5 2

By facts 3 and 5,

By facts 3 and 6c,

By facts 3,

5n2 + 7n  lim ( 5 + 7 ) = 0
lim
n!1 5lg n
n!1 n0:3 n1:3

5n2 + 7n = lim 5n + 7 = 1
lim
n!1 n ln n
n!1 ln n

By facts 3, 6a, and 6c,

By facts 3 and 4,

n lg n
lg(n!)
n=2 lg n=2
lg e
lim lg(n!)  nlim
!1 (1= lg e)n lg n = lg e nlim
!1 n ln n  nlim
!1 (1= lg e)n lg n = 2

n!1 n ln n

n=n + ln n = 1
lim n ln n = nlim
!1
8

n!1 8n + 12

By fact 3,

8n + 12 = lim (8 n + 12= n) = 1
lim
n!1 1=2
n!1

By fact 1,

lim (lg n) = 0
n!1 1=2

Exercise 2.19 P ROBLEM 2.3(CLR): Ordering by asymptotic growth rates.

You can ignore this problem

2)

2.1. GROWTH OF FUNCTIONS

15

Proof: Much of the ranking is based on the fact that: 1) exponential functions grow faster than polynomial functions,
which grow faster than logarithmic functions; 2) the base of a logarithm doesnt matter asymptotically, but the base of
an exponential and the degree of a polynomial do matter. Moreover, these identities are useful:

(log n)log n = nlog log n ;

4log n = n2 ;
2log n = n;
2 = n1= log n ;
p
p
2 2 log n = n 2= log n ;
p
p
( 2)log n = n;
log(n!) = (n log n).
Then the ordering is the following:

22n+1 ;
22n ;
(n + 1)!;
n!;

en;
n2n;

2n;
(3=2)n;
(log n)log n = nlog log n ;
(log n)!;

n3 ;
n2 = 4 log n;
n log n and log(n!);
n = 2log n ;

( 2)log n ;
p
2 2 log n ;
log2 n;
log n;
plog n;
log log n;
2log n ;
log n and log (log n);
log(log n);

n1= log n .

CHAPTER 2. MATHEMATICAL FOUNDATIONS

16

2.2 Summation
When we analyzed the insertion sort algorithm, we had to calculate the sum 1 + 2 +
+ (n , 1). In fact, it is often the
case that the analysis of algorithms reduces to calculating sums, usually more difficult than the one above.
In this section, well present a few solved exercises which reflect some usual techniques for calculation of sums,
at least for those needed in this course.

2.2.1 Some Exercises with Solutions

Exercise 2.20 Let Snk be the sum 1k + 2k + 3k +


+ nk . Then
1. Calculate Sn1 and Sn2 , and
2. Show that Snk = O(nk+1 ).

Proof:
1. We recall the formulas (x + 1)2

= x2 + 2x + 1 and (x + 1)3 = x3 + 3x2 + 3x + 1. Then

Sn2 = 12 + 22 + 32 +


+ n2
=
=
=
=
=

1 + (1 + 1)2 + (2 + 1)2 +


+ ((n , 1) + 1)2

1 + (12 + 2
1 + 1) + (22 + 2
2 + 1) +


+ ((n , 1)2 + 2(n , 1) + 1)
(12 + 22 +


+ (n , 1)2 ) + 2(1 + 2 +


+ (n , 1)) + n
(Sn2 , n2 ) + 2(Sn1 , n) + n
Sn2 + 2Sn1 , n(n + 1):

Simplifying by Sn2 , one gets Sn1

Similarly,

= n(n2+1) .

Sn3 = 13 + 23 + 33 +


+ n3

= 1 + (1 + 1)3 + (2 + 1)3 +


+ ((n , 1) + 1)3

= 1 + (13 + 3
12 + 3
1 + 1) + (23 + 3
22 + 3
2 + 1)+



+ ((n , 1)3 + 3(n , 1)2 + 3(n , 1) + 1)
= (13 + 23 +


+ (n , 1)3 ) + 3(12 + 22 +


+ (n , 1)2 )+
+3(1 + 2 +


+ (n , 1)) + n
= (Sn3 , n3 ) + 3(Sn2 , n2 ) + 3Sn1,1 + n
= Sn2 + 3Sn2 , n3 , 23n2 + n + 3
n(n2,1)
= Sn2 + 3Sn2 , n(2(n2 +3n,21),3(n,1))
n+1)
= Sn2 + 3Sn2 , n(2n +3
2
n
(
n
+1)(2
n+1) :
= Sn2 + 3Sn2 ,
2

n+1) .
= n(n+1)(2
6
We recall that (n + 1)k+1 = nk+1 + (k + 1)nk + Pk,1 (n), where Pk,1 is a polynomial of degree k , 1. Then

Simplifying by Sn3 , one gets Sn2

2.

Snk+1 = 1k+1 + 2k+1 + 3k+1 +


+ nk+1

= 1 + (1 + 1)k+1 + (2 + 1)k+1 +


+ ((n , 1) + 1)k+1

= 1 + (1k+1 + (k + 1)
1k + Pk,1 (1)) + (2k+1 + (k + 1)
2k + Pk,1 (2))+



+ ((n , 1)k+1 + (k + 1)
(n , 1)k + Pk,1 (n , 1))
= (1k+1 + 2k+1 +


+ (n , 1)k+1 ) + (k + 1)(1k + 2k +


+ (n , 1)k )+
+(1 + Pk,1 (1) + Pk,1 (2) +


+ Pk,1 (n , 1))
= (Snk+1 , nk+1 ) + (k + 1)(Snk , nk ) + O(nk )
= Snk+1 + (k + 1)Snk , nk+1 + O(nk )

Simplifying Snk , one gets Snk

+1
= nkk+1
, O(nk ), that is, Snk = O(nk+1 ).

2.3. RECURRENCE

17

Xn k2k and Xn k 2k.

2

Exercise 2.21 Calculate the sums

Xxk =
n

Proof: Recall that

k=0
n

k=0
n
+1
x ,1

x,1

X kxk,

k=0

k=0

. By differentiation, one obtains:

n
n+1
n+1
xn + 1 :
= (n + 1)x ((xx,,1)1)2, x + 1 = nx ,(x(n,+1)1)
2

Multiplying by x, one gets:

Xn kxk = nxn

+2

k=0

Xn k2k = (n , 1)2n

and replacing x by 2,

+1

k=0

, (n + 1)xn + x ;
(x , 1)
+1

()

+ 2.

Differentiating () again, one obtains

Xn k xk,
2

k=0

n+1 , (n + 1)2 xn + 1)(x , 1)2 , 2(x , 1)(nxn+2 , (n + 1)xn+1 + x)

= (n(n + 2)x

(x , 1)4

Replacing x by 2, we obtain:

Xn k 2k,
2

k=0
n
that is,

= n(n + 2)2n+1 , (n + 1)2 2n + 1 , 2(n2n+2 , (n + 1)2n+1 + 2) = (n2 , 2n + 3)2n , 3;

Xk 2k = (n
2

k=0

, 2n + 3)2n , 6.
+1

Other Exercises
Exercise 2.22 Calculate

Xn 1 .
k

k=1 2

Exercise 2.23 Evaluate

Xn k2k, where n is an exact power of 2.

Exercise 2.24 Calculate

X k(k + 1).

log

k=0
n

k=1

2.3 Recurrence
The running time analysis of most divide and conquer algorithms reduces to solving a recurrence formula. More
precisely, if A is a divide and conquer algorithm which divides the original problem of size n into a subproblems of
smaller sizes n1 , n2 , ..., na and then combines the solutions of the subproblems into a solution for the original problem
in time f (n), then the running time of A on an input of size n is given by the recurrent formula:

T (n) = T (n1) + T (n2) +


+ T (na ) + f (n):

When the size of the subproblems are small enough, say smaller than a constant n0 , their output can be generated in a
number of steps which doesnt depend on the size of the original problem.

CHAPTER 2. MATHEMATICAL FOUNDATIONS

18

In general, the a subproblems have the same size which is a fraction of n, say n=b, in which case the recurrence
formula has the form

T (n) = aT (n=b) + f (n):

For example, the analysis of merge sort reduced to solving a recurrence of the same form, for a = b = 2 and f (n) = n,
since the original problem of size n was divided in two subproblems of size n=2, whose solutions needed n time steps
to combine. We pay more attention to solving this special case of recurrences, even though some of the methods
presented below also work for general recurrences. There are three usual methods for solving recurences; we present
them in the sequel.

2.3.1 Recursion Tree Method

This is perhaps the most intuitive method for solving recurrences. It basically consists of drawing a tree whose nodes
represent the sizes of corresponding subproblems and whose down-edges from a node represent the subproblems of
the corresponding problem. Thus each subproblem solved (or conquered) during the execution of the algorithm
belongs to exactly one level in the tree, and each level i contains all those subproblems of depth i. There are two
important issues which one should consider: the height of the tree and the number of time steps on each level. The
solution of the recurrence, or the running time of the corresponding algorithm, is the sum of all time steps at all the
levels in the tree. In particular, when the same number of time steps at each level is the same, say l(n), then the
solution is T (n) = h
l(n), where h is the height of the tree. The following is a recursion tree for the recurrence
T (n) = 2T (n=2) + n of merge sort:

Time steps
n

n/2
n/4

n/2
n/4

n/4

2 * (n/2) = n
n/4

4 * (n/4) = n

h
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

n/2

h = log n

n/2

n/2

2 * (n/2 ) = n
Total time = h * n

The height of this tree is h = log n because the size of the subproblems at level h is n=2h , which does not depend
on n anymore, so they can be solved in time (1).

2.3.2 Iterative Method

The iterative method is an algebrization of the more intuitive recursion tree method. It consists of unfolding the
recurrence for as many steps as needed to capture a summation which once solved yields a solution to the original
recurrence. The iterative method is more rigurous than the recursion tree method, so the likelyhood to do mistakes is
smaller. On the other hand, it may require deeper mathematical knowledge.

2.4. SOME EXERCISES WITH SOLUTIONS

19

Lets use the iterative method to calculate (again) the running time of merge sort:

T (n) = 2T (n=2) + n
= 2(2T (n=4) + n=2) + n
= 22T (n=22) + 2n
2
3
2
= 2 (2T (n=2 ) + n=2 ) + 2n = 24T (n=23) + 3n
..
.

= 2h T (n=2h) + hn

=
=

(after h unfoldings).

We keep unfolding the recurrence until n=2h becomes small enough to not depend on n, for example 1. Then h = log n
(dont worry if h is not an integer), so T (n) = 2log n T (1) + n log n = nT (1) + n log n 2 (n log n).

2.3.3 Master Method

There is a magic theorem solving almost any recurrence:
Master Theorem. Let T (n) = aT (n=b) + f (n) be a recurrence. Then
1. If f (n) 2 O(nlogb a, ) for some  > 0 then T (n) 2 (nlogb a );

2. If f (n) 2 (nlogb a ) then T (n) 2 (nlogb a log n);

3. If f (n) 2
(nlogb a+ ) for some 
then T (n) 2 (f (n)).

> 0, and if af (n=b)  cf (n) for some c > 0 and all sufficiently large n,

In the case of merge sort where a = b = 2 and f (n) = n, we have that logb a = 1, so we are in the second case of
the theorem. Hence T (n) 2 (n).
The proof of the master theorem is complex and we are not going to approach it in this course. This theorem is
very elegant and often easy to use, but we warn the reader that it can sometimes be very tricky, especially its third
case. We recommmend you avoid using it whenever possible in this course; use recurrsion trees or iterative methods
instead, or use only its second case which is the easiest to check.

2.4 Some Exercises with Solutions

Exercise 2.25 Argue that the solution to the recurrence T (n)
to a recursion tree.

= T (n=3) + T (2n=3) + n is
(n log n) by appealing

Proof: The shortest path from the root to a leaf in the recursion tree is n ! (1=3)n ! (1=3)2 n !


! 1. Since
(1=3)k n = 1 when k = log3 n, the height of the part of the tree in which every node has two children is log3 n. Since
the values at each of theses levels of the tree add up to n, the solution to the recurrence is at least n log3 n =
(n log n).
Exercise 2.26 Solve the recurrence T (n) = T (

pn) + 1.

Proof: First, make the substitution n = 2m and let S (m) denote T (2m ). Replacing n with 2m , we obtain the
recurrence T (2m ) = T (2m=2 ) + 1, that is, S (m) = S (m=2) + 1. Solving this equation using trees, we get the
solution S (m) = O(log m). Replacing S (m) with T (2m ), one obtains T (2m ) = O(log m), which means that
T (n) = O(log log n).

Exercise 2.27 A divide an conquer algorithm A splits the original problem in two related subproblems of size n
and then needs log n time to combine the solutions of the subproblems into a solution for the original problem. Whats
the running time of A?

Proof: The recurence for the running time of A is (1 point)

T (n) = 2T ( n) + log n:
m
Lets solve this recurence (1 point) now. Substituting n = 2m , we get that T (2m ) = 2T (2 2 ) + m; notice that
m = log n. Further, substituting S (m) = T (2m), we obtain the new recurence S (m) = 2S (m=2) + m which is the
same as the one for merge sort, so its solution is S (m) = m log m. Substituting back S (m) = T (2m ) and m = log n,
we obtain that T (n) = log n
log log n.

CHAPTER 2. MATHEMATICAL FOUNDATIONS

20

Exercise 2.28 The running time of an algorithm A is described by the recurrence T (n) = 7T (n=2)+ n2. A competing
algorithm has a running time of T 0 (n) = aT 0 (n=4) + n2 . What is the largest integer value for a such that A0 is
asymptotically faster than A?

Proof: Using the tree method or the master theorem, we can obtain that T (n) = O(nlog2 7 ) and that T 0 (n) =
O(nlog4 a ). Now it is easy to observe that A0 is asymptotically faster than A if and only if log4 a < log2 7. This holds
when a < 49.

Exercise 2.29 The mode of a set of numbers is the number that occurs most frequently in the set. The set (4,6,2,4,3,1)
has a mode of 4.
1. Give an efficient and correct algorithm to compute the mode of a set of n numbers;
2. Suppose we know that there is an (unknown) element that occurs n=2 + 1 times in the set. Give a worst-case
linear-time algorithm to find the mode. For partial credit, your algorithm may run in expected linear time.

Proof:
1. A simple algorithm for this problem is to sort the n numbers, and then traverse the sorted array keeping track of
the number with the highest frequency
Inputs: array of numbers S indexed from 1 to n.
Outputs: the number within the set with the highest frequency.
F IND M ODE(S ,n)
1.
2.
3.
4.
5.
6.
7.
8.
9.

M ERGESORT(S ,n)
current = S [1]
count = 0
for i = 2 to n
if (S [i] = current)
count = count +1
else
count = 0; current = S [i]
return current

This algorithms worst-case running time is (n lg n) due to the M ERGESORT being performed in step 1. The
algorithm works because after the set is sorted identical numbers will be adjacent. Therefore, with a linear scan of the
array we can find the number with the highest frequency.
b) (Solution 1) A (n) expected-time algorithm uses the partition procedure from quicksort. A randomly chosen
partition element will be used to split the array into two halves. If the partition element is less than the mode (the
element which occurs n=2+1 times), then the partition element will end up in a position in the range (1 : : : (n=2) , 2).
In other words, if the partition element ends up in a position to the left of the center, the mode will be in the set of
numbers to the right of the partition element. If the partition element is greater than the mode the partition element
will be in position n=2 + 2 or greater, and the mode will be in the set of numbers to the left of the partition element.
Therefore, after each partition we can recursively call our algorithm on the set of numbers which includes the mode.
When the size of the set is 1 then that element is our answer. The running time in the average-case is T (n) =
T (n=2) + n = (n).
Inputs: array of numbers A in which one number appears n=2 + 1 times, starting index low, ending index high.
Outputs: the number within the set with the highest frequency.

F IND M ODE(A,low,high)

1. if (low = high)
2. return A[low]
3. if (low < high)
4. ploc = PARTITION(A,low,high)
5. if ploc > bn=2c + 1
6.
F IND M ODE(A,low,ploc , 1)
7. else

2.4. SOME EXERCISES WITH SOLUTIONS

8.

21

F IND M ODE(A,ploc + 1,high)

b) (Solution 2) We can use a more exact divide and conquer scheme to get a worst-case running time of (n). We
will divide the set by doing bn=2c pairwise comparisons and only keeping one representative of the pairs which are
equal. When n is even, at least one of the n=2 comparisons will yield an equality because there are n=2 + 1 of the
same element(the mode) in the set. Anytime a number other than the mode is part of an equality, the mode will also be
part of another equality. Therefore the number of equalities will be 2k + 1 where k is an integer  0 and k + 1 of the
equalities will involve the mode. Therefore, we can call our function recursively on the 2k + 1 representatives from
the equalities, and the new set will still maintain the attribute of having at least bn=2c + 1 of one element. When n is
odd, there will be a leftover element after the bn=2c comparisons are done. If the number of representatives left after
doing the comparisons is 2k , where k is an integer  0, then the left out element should be included because it is the
mode. This is because if there are 2k equalities from the bn=2c comparisons then at least k of those equalities involve
the mode, but the other k could involve another number so the left out element must be included. On the other hand,
if there are 2k + 1 equalties then the left out element should not be included in the new set.
Inputs: set of numbers S in which one number appears n=2 + 1 times, the size of the set n
Outputs: the number within the set with the highest frequency.

F IND M ODE(S , n)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

if n = 1 then return S [1]

Snew =
nnew = 0
for i = 1 to bn=2c by 2
if (S [i] = S [i + 1]) then
nnew = nnew S
+1
Snew = Snew S [i]
if (n mod 2) = 1 // n is odd

if (count mod 2) = 1

Snew = Snew S [n]

nnew = nnew + 1
return F IND M ODE(Snew ,nnew )

Each time F IND M ODE is recursively called with a smaller problem which is at most size dn=2e. At each step in
the recursion bn=2c comparisons are performed. Therefore, the total running time of the algorithm is

T (n)  T (dn=2e) + bn=2c

The solution to this recurrence is T (n) = O(n).
b) (Solution 3)
Ignore this solution, it uses notions that you may not know yet.
If an element occurs more than n=2 times, then that element will necessarily be the median element. So, the Select
algorithm can be used to find that element in deterministic linear time. However, this algorithm has a high constant
and so it may be slow in practice.
Exercise 2.30 Professor Diogenes has supposedly identical VLSI chips that in principle are capable of testing each
other. The professors test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and
reports wheter it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the
answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows:
Chip A says
B is good
B is good
B is bad
B is bad

Chip B Says
A is good
A is bad
A is good
A is bad

Conclusion
both are good, or both are bad
at least one is bad
at least one is bad
at least one is bad

CHAPTER 2. MATHEMATICAL FOUNDATIONS

22

a) Show that if more than n=2 chips are bad, the professor cannot necessarily determine which chips are good using
any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.
b) Consider the problem of finding a single good chip from among n chips, assuming that more than n=2 of the chips
are good. Show that bn=2c pairwise tests are sufficient to reduce the problem to one of nearly half the size.
c) Show that the good chips can be identified with (n) (proportional to n) pairwise tests, assuming that more than
n=2 of the chips are good. Give and solve the recurrence that describes the number of tests.

Proof: Question a): Let g be the number of good chips and n , g be the number of bad chips. Also, assume n , g  g .
From this assumption we have that we can always find a set G of good chips and a set B of bad chips of equal size
g. Now, assume that the set B of bad chips conspire to fool the professor in the following way: for any test made by
the professor, they declare themselves as good and the chips in G as bad. Notice that the chips in G report correct
answers and then exhibit a symmetric behaviour: they declare themselves as good and the chips in B as bad. This
implies that whichever is the strategy based on the kind of test considered and used by the professor, the behaviour of
the chips in G is indistinguishable from the behaviour of the chips in B . This does not allow the professor to determine
which chips are good.
Question b): Assume n is even. Then we can match chip in pairs (c2i,1 ; c2i ), for i = 1; : : : ; n=2 and test all these
pairs. Then we throw away all pairs of chips that do not say good, good and finally we take a chip from each pair. In
this way, the final set contains at most n/2 chips and we are still keeping more good chips than bad ones, since all the
pairs that we have discarded contain at least a bad chip.
Now, assume n is odd. Then, we test bn=2c pairs constructed as before; this time, however, we dont test one chip,
say, cn . Our final set will contain one chip for every pair tested that reported good, good. Moreover, according to
whether the number of such chips has the form 4k + 3 or 4k + 1, we discard chip cn or we put it into our final set.
Now, why this construction works ?
First of all, as in the case in which n is even, by discarding all pairs of chips that report anything but good,good, we
discard pairs of chips in which at least one is bad, and thus we still keep more good chips than bad ones.
Now, assume that we have discarded the pairs of chips that report anything but good,good, and we are left with 4k +3
chips, for some integer k . Then, in this case there are at least 2k + 2 good chips and thus there are at least k + 1 pairs
of good,good chips, and at most k pairs of bad,bad chips. Thus chip cn can also be discarded, and only a chip in
each of these 2k + 2 pairs is not discarded.
Finally, assume that we have discarded the pairs of chips that report anything but good,good, and we are left with
4k + 1 chips, for some integer k. Then, in this case there are at least 2k + 1 good chips.

Now, assume cn is bad; then there are at least 2k + 2 good chips, that is, k + 1 pairs of good,good chips; and at most
k , 1 pairs of bad chips. Thus, taking a single chip from every pair, plus cn gives us at least k + 1 good chips and at
most (k , 1) + 1 = k bad chips; that is, a majority of good chips and our final set is at most of size dk=2e.
On the other hand, assume cn is good. Then we have at least k pairs of good,good chips and taking a chip from each
pair plus cn gives us a majority of good chips and a final set of size at most dk=2e.

Question c): If at least n=2 of the chips are good, using the answer to question b), we can compute a single good
chip. Now, in order to find all good chips, we can just test the good chip with all the others: for each pair of this type,
knowing that at least one of the two chips in the pair is good is enough to decide whether the other chip is good or not.
This last stage takes n , 1 more tests. Then, in order to prove that the goof chips can be found with (n) pairwise
tests, we just need to show that the number of tests to find a single good chip is (n). To show this, we can write the
number of tests T (n) that we do in the answer to question b) as

T (n)  T (dn=2e) + bn=2c;

and T (1) = 0. The solution to this recurrence is
proving by induction that T (n)  2dlog ne .
Exercise 2.31 This problem has three parts:
1. Solve the recurrence T (n) = T (n=2) + n.

T (n) = O(n) and can be computed for instance by arguing and

2.4. SOME EXERCISES WITH SOLUTIONS

23

2. You are a young scientist who just got a new job in a large team of 100 people (you the 101-st). A friend of
yours who you believe told you that you have more honest colleagues than liars, and that thats all what he can
tell you, where a liar is a person who can either lie or tell the truth, while an honest person is one who always
tells the truth. Of course, youd like to know exactly your honest colleagues and the liars, so that you decide
to start an investigation, consisting of a series of questions you are going to ask your colleagues. Since you
dont wish to look suspicious, you decide to ask only questions of the form Is Mary an honest person? and of
course, to ask as few questions as possible. Can you sort out all your honest colleagues? Whats the minimum
number of questions youd ask in the worst case? You can assume that your colleagues know each other well
enough to say if another person is a liar or not. (Hint: Group people in pairs (X,Y) and ask X the question Is
Y honest? and Y the question Is X honest?. Analyze all the four possible answers. Once you find an honest
person, you can easily find all the others. Challenge: can you solve this enigma asking less than 280 questions
in total?)
3. Generalize the strategy above and show that given n people such that less then half are liars, you can sort them
out in honest persons and liars by asking O(n) questions.
Proof: The role of 1 is to suggest you that you should reduce the problem to a related subproblem of size half the
size of the original problem. Additionally, the recurrence in 1 is closely related to the recurence obtained in 3.
1. Since T (n)  n, we immeditely get that T (n) 2
(n). On the other hand, since

1 + 21 + 212 +


21k  2;
unwinding the recurence we obtain:

T (n) = T ( n2 ) + n
= T ( 2n2 ) + n(1 + 21 )
..
.

= T ( 2nk ) + n(1 + 12 + 212 +


+ 2k1,1 )

..
.

 T (1) + n(1 + 12 + 21 +


+ 2 1n, )

 T (1) + 2n
2 O(n):
2

log

Therefore, T (n) 2 (n).

2. Our first goal is to find a honest person. Group your colleagues in pairs (X; Y ) and ask X the question Is Y
honest? and Y the question Is X honest?. A first important observation is that at least one of X , Y is a liar
whenever you get at least a NO answer; then you can remove both X and Y from the set of potential honests,
because the remaining n , 2 people still verufy the property that more than half are honest. Therefore, well
keep only those pairs whose answers are YES, noticing that either both people in each group are honest or both
are liars.

Let T (n) be the number of questions (the running time :) you need to ask a group of n people with more honests
than liars, in order to find a honest person. We are looking for a recurence for T (n). There can be distinguished
three cases, depending on the number of pairs answering (YES,YES) and the parity of people:
(a) Even number of people grouped in k pairs. Then we can remove one person from each pair, the remaining
k people still having the property that more than half are honest. Thus, we obtain the recurrence

T (2k)  T (k) + 2k;

because we asked 2k questions to reduce the problem by half. The worst case is of course when n = 2k ;

CHAPTER 2. MATHEMATICAL FOUNDATIONS

24

(b) Odd number of people, grouped in even number of pairs 2k and one person singled out. Then we can
remove one person from each pair, obtaining the recurrence

T (4k + 1)  T (2k + 1) + 4k;

since we asked questions only the 4k people grouped in pairs;

(c) Odd number of people grouped in odd number of pairs 2k + 1 and one person singled out. Then we can
safely remove one person from each group together with the singled out one, obtaining the recurrence

T (4k + 3)  T (2k + 1) + 4k + 2:
Applying the divide and conquer technique described above in which about half the people are removed each
step, we can calculate the number of questions needed in the worst case to detect an honest out of 100:

T (100)
T (50)
T (25)
T (13)
T (7)
T (3)
T (1)
T (100)







=

T (50)
T (25)
T (13)
T (7)
T (3)
T (1)

+ 100
+ 50
+ 24
+ 12
+ 6
+ 2
0
194

Once an honest person is found, say X , then we might ask X 99 questions and thus completely correctly divide
the 100 people in honests and liars. Therefore, we apparantly need 293 questions in total.

However, it can be done better! We do not need to ask X 99 questions, but to reuse the information we have
from previous questions we asked X . For example, during the division of the problem into subproblems, we
asked X 6 questions about other 6 people and we got answers YES, so we already knwo that those 6 people are
honest. Moreover, each of the known 6 people were asked questions about other people who were previously
removed, so those people are also honest. This procedure can be iterated and reduce the number of questions
for X by 63! Thus, the total number of questions needed to find all the honest people is 230. I do not see how
to do it better.
3. We can upper bound the recurrence above by another more compact recurrence T (n)
solution is in O(n).

 T (3n=4) + n, whose

Exercise 2.32 Problem 1.2-4(CLR) Consider the problem of evaluating a polynomial at a point. Given n coeffin,1
cients a0 ; a1 ; : : : ; an,1 and a real number x, we wish to compute i=0 ai xi . Describe a straightforward (n2 )-time
algorithm for this problem. Describe a (n)-time algorithm that uses the following method (called Horners rule) for
rewriting the polynomial:

X a xi = (


(a

n,1
i=0

n,1 x + an,2 )x +


+ a1 )x + a0 :

One cannot assume the existence of functions that compute the power xi , but only of functions that compute sums and
multiplications.
Proof: The straightforward (n2 )-time algorithm is made of a for loop to compute the power xi and another for loop
n,1
to compute the sum i=0 ai xi .

STRAIGHTFORWARD(a; x)
1.
2.
3.

sum a0 ;
for i = 1; : : : ; n , 1,
y 1;

2.4. SOME EXERCISES WITH SOLUTIONS

for j

4.
5.
6.
7.

25

= 1; : : : ; i,

y y  x;
sum sum + ai  y;
return(sum).

In the above algorithm, line 5 is executed n(n , 1)=2 times, thus the running time is (n2 ). A (n)-time algorithm
can be designed using Horners rule in the following way: in the above formula, the summation is written using n
parenthesis; then, the idea is to keep track of the partial results computed in the parenthesis.
HORNER(a; x)
1.
2.
3.
4.

sum an,1 ;
for i = n , 2; : : : ; 0,
sum sum  x + ai ;
return(sum).

Exercise 2.33 Tree isomorphism Give an efficient algorithm to decide , given two rooted binary trees T and T 0 ,
whether T and T 0 are isomorphic as rooted trees.

Proof: Let root be the root of T and root0 be the root of T 0 , and let L; R; L0 ; R0 be the left and right subtrees of T
and T 0 respectively. If T embeds in T 0 , then the isomorphism f must map root to root0 , and must map every member
of L either entirely to L0 or entirely to R0 and vice versa. Thus, we can define the isomorphism relationship Iso on
sub-trees as follows: Iso(NIL; NIL) = True, Iso(x; NIL) = Iso(NIL; x) = False if x 6= NIL and otherwise

Iso(r1 ; r2 ) =
(Iso(Left(r1 ); Left(r2 ))ANDIso(Right(r1 ); Right(r2 )))
OR

(Iso(Left(r1 ); Right(r2 ))ANDIso(Right(r1 ); Right(r2 )):

The above immediately translates into a program, and the time, I claim, is O(n2 ) . The reason is that for any nodes

x 2 T; y 2 T 0, the above calls itself on x; y at most once (in fact, precisely when x and y are at the same depths of
their trees.) Let P be the path from Root to x and P 0 be that from Root0 to y ; in a tree there is exactly one such
path. Then, of the four recursive calls at any level, at most one involves nodes from both P and P 0 . Inductively, at any
recursion depth, at most one call compares a sub-tree containing x to one containing y . Since all sub-trees called at
depth d of the recursion are depth d in their respective trees, the claim follows. Therefore the total number of calls is
at most O(n2 ).
Exercise 2.34 Show that the second smallest of n elements can be found with n + dlog ne , 2 comparisons in the
worst case.

Proof: The smallest of n numbers can be found with n , 1 comparisons, by conducting a tournament, as follows:
compare all the numbers in pairs, consider the set of elements having the smaller element for each pair and repeat the
same on this set. The problem is reduced each time by half, and the number of comparison is n=2+ n=4+ n=8+


+
1 = n , 1. Graphically, the tournament can be represented as a binary tree, where the root is the minimum and for each
node u, his two children u and v were the two elements, such that from their comparison, u came out smaller. Then
the second smaller element is clearly one of the elements that have been compared to the smallest element, coming
out bigger from such comparison. Since the height of the tree is at most dlog ne, finding the second smallest will take
at most dlog ne , 1 additional comparisons. Thus the total number of comparisons is n + dlog ne , 2.

Exercise? 2.35 i-th largest elements

with n + O(log n) comparisons.
Proof:

Show that, for any constant i, the i-th largest element of an array can be found

CHAPTER 2. MATHEMATICAL FOUNDATIONS

26
This is a hard problem. Skip it if you get lost ...

First, note that in any comparison algorithm to find the ith largest in the array, we must compare the ith largest
element to the i + 1st largest. (Otherwise, the algorithm would give the same answer if we increased the array
position where the i + 1st element is to be between the ith and i , 1st largest.)
Well use this to prove by induction on i that there is a comparison algorithm and constants ci ; di so that the
algorithm makes a total of at most n + ci log n comparisons and no element is compared to more than di log n other
elements.
First, the base case is when i = 1. We claim we can find the largest element while making n , 1 comparisons,
without comparing any element to more than log n elements, so the claim is true for c1 = 0; d1 = 1. We do this by
finding the maximum through a divide-and-conquer approach, recursively finding the maximum of the first and last
n=2 elements, and returning the maximum. The number of comparisons is easily seen to be n , 1 by solving the
recurrence, or by observing that every element but the largest is the smaller element in exactly one comparison the
algorithm makes. No element is compared to more than log n others, since there are log n recursion levels, and each
element is only in one sub-array at any recursion level.
Assume we have an algorithm that finds the ith largest element in n + ci log n comparisons, making no more than
di log n comparisons with any particular element. To find the i + 1st largest, we run the above algorithm, and then
look at all elements compared to the ith largest, and found to be smaller. There are at most di log n such elements.
As observed above, the i + 1st largest element must be in this set, and it must be the largest in this set, since all
elements are less than the ith largest. So we find the maximum using the approach in the base case, and output it.
This uses at most di log n additional comparisons, so we can let ci+1 = ci + di . No one element is compared more
than log(di log n) < log n additional times, so we can let di+1 = di + 1.
Thus, by induction, for every i there is a comparison algorithm that finds the ith largest in n + O(log n) comparisons.
Exercise? 2.36 k -way merging Give tight upper and lower bounds in the comparison model for merging k sorted
lists with a total of n elements. Lower bounds should be for any algorithm, not just the upper bound algorithm.
Proof:
This is another hard problem. Skip it if you find it too difficult
An O(n log k ) algorithm for the problem is to pair the lists umerge each pair, and recursively merege the k=2 resulting
lists. The time is given by the recurrence T (n; k ) = O(n) + T (n; k=2), since the time to perform the merge for
each pair of lists is proportional to the sum of the two sizes, so a constant amount of work is done per element. Then
unwinding the recurrence gives log k levels each with O(n) comparisons, for a total time of O(n log k ).
One way to prove the lower bound for any algorithm is to use our lower bound for sorting of n log n , O(n) and
the upper bound for mergesort of n log n comparisons to reduce the question of sorting n unordered elements to that
of merging k sorted lists of total size n as follows.
Let A be a correct algorithm for merging k lists that runs in time T (n; k ). Well prove T (n; k )  n log k , O(n)
as follows. Let A , Sort be the algorithm that takes an array of n elements and divides it into k sub-arrays of at most
n=k elements each and at most k leftover elements. It sorts each sub-array using mergesort , which takes at most k
times n=k log(n=k ). It then places each left-over element within an array, making less than k (n=k ) = n comparisons.
It calls A on the resulting set of sorted sub-arrays, resulting in a sorted list.
The total number of comparisons for A , Sort is at most n log(n=k ) + n + T (n; k ). Since any algorithm for
sorting takes at least n log n , O(n) comparisons, T (n; k ) + n log(n=k ) + n  n log n , O(n), so T (n; k ) 
n log n , n log(n=k) , O(n) = n log n , n log n + n log k , O(n) = n log k , O(n).
An alternative method for proving a lower bound is to use a counting argument similar to that used to prove

(n=lgn) for single list sorting. In order for an algorithm to succesfully sort all k-lists of a total of n elements, it
must in particular distinguish all partitionings of 1::n into k sorted lists of n=k elements each. There are at least
Nn;k = (k!)n=k such lists. Which is Nn;k > (k=2)(k=2)(n=k) , and therefore log Nn;k > cn log k or
(n log k).

Other Exercises
Exercise 2.37 Solve T (n) = T (n=2) + 1.

2.4. SOME EXERCISES WITH SOLUTIONS

Exercise 2.38 Solve T (n) = T (n=2) + n.
Exercise 2.39 Solve T (n) = 2T (

pn) + 1.

Exercise 2.40 Solve T (n) = 3T (n=2) + 2.

Exercise 2.41 Solve T (n) = T (2n=3) + 1.
Exercise 2.42 Solve T (n) = 4T (n=2) + n2 .

27