COMP2711: Algorithms and Data Structures I

Session 2023-24
Semester 1

Natasha Shakhlevich
School of Computing, Room 3.39
 1. Module Overview and Introduction
Texts
A. Levitin (2012) Introduction to the Design and Analysis of Algorithms, Addison Wesley
M.T. Goodrich, R. Tamassia (2002) Algorithm design: foundations, analysis, and internet
examples, John Wiley & Sons
R.F. Gilberg, B.A. Forouzan (2001) Data structures: a pseudocode approach with C++,
Brooks/Cole
F.M. Carrano, J.J. Prichard (2011) Data Abstraction and Problem Solving with Java: Walls
and Mirrors, Addison Wesley
or Data Abstraction and Problem Solving with C++: Walls and Mirrors
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein (2009) Introduction to Algorithms, MIT
Press
A.V. Aho, J.E. Hopcroft, J.D. Ullman (1983) Data structures and algorithms, Addison Wesley

Module plan
Analysis of algorithms - iterative algorithms
- recursive algorithms
Searching algorithms - sequential search
- binary search
Sorting algorithms - selection sort
- insertion sort
- bubble sort
- merge-sort
- quick-sort
Basic data structures - arrays, lists
- stacks
- queues
- priority queues; heap-sort

1.1 Why do you need to study algorithms?

❑ To learn useful algorithm design techniques (several general design strategies will
be discussed)
❑ To demonstrate that your solution method terminates and it produces a correct
answer
❑ To evaluate algorithm’s efficiency
❑ To learn a standard set of important algorithms and data structures
- algorithms toolkit
- data structure toolkit
Modern computers are
- fast but not infinitely fast
- memory is limited
- memory is cheap but not free

The choice of an algorithm and data structure can make the difference between a
program running in a few seconds or many days.

1
 Examples:
Human genome – identifying thousands of genes in human DNA,
determining the sequences of 3 bln pairs that make up human DNA
Internet technology – finding good routes for data to travel
Cryptography – secure communication: methods based on numerical algorithms and
number theory
Optimisation – scheduling patients in a hospital,
university timetable
optimising allocation of scarce resources
business analytics
Processing Big Data efficiently

Donald E. Knuth: “People who analyze algorithms have double happiness. First of all
they experience the sheer beauty of elegant mathematical patterns that surround
elegant computational procedures. Then they receive a practical payoff when their
theories make it possible to get other jobs done more quickly and more economically.”
Follow-up reading
- What are the main books by Donald Knuth?
- $2.56 for finding errors: what is the meaning of “2.56”?

1.2 What is an algorithm?

The word algorithm derives from the name of the famous Persian mathematician
Mohammed ibn-Musa Al-Khowarizmi (Algorismus in Latin) who lived from about 780
to 850. Among his contributions are
- procedures for arithmetic operations using decimal numbers
- procedures for solving linear and quadratic equations
- the concept of an algorithm: any mathematical problem, no matter how difficult,
could be solved if broken down into a series of smaller steps

Input

Data Structure

Algorithm
Systematic way of
organising and A step-by-step procedure for solving a problem
accessing data

Output
An algorithm is not an answer; it is a set of instructions for getting answers.
Properties of an algorithm
1) It must be composed of a series of concrete steps.
2) It must terminate after a finite number of steps.
3) There must be no ambiguity as to which step will be performed next.
4) It must be correct.

2
 Compare the following two algorithms for finding the largest number.

Input a, b, c
Compare a and b; find the largest and assign it to variable x.
Compare c and x; update x, if required.
return x

ALGORITHM Find-Largest(a,b,c)
//The algorithm for finding the maximum of three numbers
//Input: integers a, b, c
//Output: integer x
x  a
if b > x
x  b
if c > x
x  c
return x

Which version is preferable and why?

1.3 What is a pseudocode?

Pseudocode resembles the actual code in Python, C++, Java, but it is more relaxed. Still it
is precise and has a clear structure.

Programming language Pseudocode

input/output operators brief descriptions
variable declarations N/A
Arrays of fixed size A[0..n-1]
syntax rules Relaxed syntax, without { } ;
<= 
!= 
various technical details shorthand descriptions

3
 Basic pseudocode constructs:
- assignment i  1

- if condition if i<n
then action (1) application code (1)
else action (2) else
application code (2)

- for-loops for i1 to n do

application code

- while-loops i  1
while in do
application code
Read about i  i+1
Edsger Dijkstra and the structured
programming paradigm

1.4 Steps in program development

Define the problem
- input
- output

Algorithm design
- rough sketch of main steps
- pseudocode

Desk checking
- tracing with test data

Algorithm analysis

Coding, debugging
testing, maintaining

1.5 What is analysis of algorithms?

A problem can have many algorithms.
Example: Many algorithms are known for the travelling salesman problem (TSP, finding
the shortest tour passing through n cities). A simple algorithm can be noticeably
inefficient.
Read about the TSP at
www.math.uwaterloo.ca/tsp
4
 An algorithm is said to be efficient if it solves the problem within its resource
constraints.
- Space
- Time
The cost of a solution is the amount of resources that the solution consumes.
Time efficiency indicates how fast an algorithm runs.
Space efficiency deals with the space the algorithm requires (for example, some
sorting algorithms operate “in place”, others need extra memory).

2. Iterative Algorithms and Their Analysis

Empirical analysis: efficiency of an algorithm is analysed via computational experiments.
- Write a program implementing an algorithm
- Run the program with various inputs
- Use a method like gmtime() to get its actual running time
- Plot the results

Time (ms) Time (ms)

9000 9000

8000 8000

7000 7000

6000 6000

5000 5000

4000 4000

3000 3000

2000 2000

1000 1000
Input Input
Size Size
0 50 100 0 50 100

Theoretical analysis involves estimating the time complexity or the running time of an
algorithm.
The time complexity or the running time of an algorithm expresses the total number of
elementary operations (such as additions, multiplications and comparisons) for each
possible problem instance as a function of the size of the instance.

5
An iterative algorithm consists of statements repeated a number of times in a loop.

for i1 to n do i  1
application code while i  n do
application code
i  i + 1
If the above algorithms involve application codes which perform a constant number of basic
operations, then the following statements can be used:

▪ The running time of Algorithm A is proportional to n

▪ The running time of Algorithm A on any input of size n does not exceed cn for a
sufficiently large n, where c is a constant
▪ The running time of Algorithm A is of the order of n
▪ The running time of Algorithm A is O(n)
▪ The running time of Algorithm A is linear
▪ The time complexity is O(n)

Later on we will study recursive algorithms. A recursive algorithm also represents a

repetitive process but instead of using loops, it solves a problem by solving a smaller
instance of the same problem.

Examples of iterative algorithms

i  1 assume the appl.

there are n iterations code performs a
while i  n do
the running time is O( n ) application code constant number of
i  i + 2 operations

i  1
there are ___ iterations while i  n do
the running time is O(___) application code
i  i + 2

there are ____ iterations i  1

the running time is O(___) while i  2n do
application code
i  i + 1

6
 for i  1 to n do
i = 1 j = 1 appl.code
for j  1 to n do
j = 2 appl.code
application code
……
j = n appl.code

the appl. code is repeated n2 times i = 2 j = 1 appl.code assume

the running time is O(n2) j = 2 appl.code each appl.
… code
j = n appl.code performs
a constant
… number of
operations
i = n j = 1 appl.code
j = 2 appl.code
…
j = n appl.code

Example 1. The following algorithm finds the largest number in an array of n numbers.
ALGORITHM FindLargest(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: the largest element of the array
Largest  A[0]
for i1 to n-1 do
if Largest<A[i] LargestA[i]
return Largest

Consider array A given by the table 5 2 7 9 6 1

A[0] A[1] A[2] A[3] A[4] A[5]
Fill in the tracing table.

i Largest<A[i]? Largest

1
2
3
4
The algorithm returns ______
5
(i) What are the algorithm’s basic operations? ______________________________________
(ii) How many times are the basic operations executed? ____________________________
(iii) Determine the class O(?) the algorithm belongs to._______________________________

7
Example 2. The following algorithm verifies The operation of the nested loops can be
whether two matrices A and B are equal. illustrated as follows:
ALGORITHM equalMatrices(A,B) j = 0 appl.code
//Input: Two n-by-n matrices A,B i=0
j = 1 appl.code
//Output: “true” if A=B, …
// “false” otherwise
j=n-1 appl.code
for i0 to n-1 do
for j0 to n-1 do
i=1 j = 0 appl.code
if A[i,j]B[i,j] return false
j = 1 appl.code
return true
…
j=n-1 appl.code

i=n-1 j = 0 appl.code
j = 1 appl.code
…
j=n-1 appl.code
Consider an instance with

4 2 5 1 4 2 5 1
9 3 7 4 9 3 7 4
A= B=
0 8 11 5 0 8 1 5
5 6 9 2 5 6 9 2

Fill in the tracing table.

i A[i,j]B[i,j]? return
The algorithm returns ______

(i) What are the algorithm’s basic

operations?

(ii) How many times are the basic operations

executed?

(iii) Determine the class O(?) the algorithm

belongs to.

8
Example 3. What does algorithm Mystery1 compute?

Algorithm Mystery1(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: ?
x  A[0]
y  A[0]
for i  1 to n-1 do
if A[i] < x
x  A[i]
if A[i] > y
y  A[i]
return y–x

(i) What are the algorithm’s basic operations?

(ii) How many times are the basic operations executed?

(iii) Determine the class O(?) the algorithm belongs to.

Example 4. What does algorithm Mystery2 compute?

Algorithm Mystery2(A[0..n-1])
//Input: an array A[0..n-1] of n numbers (n is even)
// Output: ?
for i  0 to n/2–1 do
tmp  A[i]
A[i]  A[n-i-1]
A[n-i-1]  tmp
return A[0..n-1]

(i) What are the algorithm’s basic operations?

(ii) How many times are the basic operations executed?

(iii) Determine the class O(?) the algorithm belongs to.

9
 3. Dependent Nested Loops

In this section we consider an example of an The operation of dependent nested loops

algorithm, in which the inner loop depends can be illustrated as follows:
on the control variable of the outer loop.
i=1 j = 1 appl.code
for i  1 to n do
for j  1 to i do
application code i=2 j = 1 appl.code
j = 2 appl.code
…

i=n j = 1 appl.code
j = 2 appl.code
…
j = n appl.code

The number of iterations is 1+2+…+n = ½ n(n+1)

Example. Consider the problem of calculating prefix averages.

Given an array X[0..n-1] of n numbers, compute array A[0..n-1] such that A[i] is
the average of elements X[0], X[1], …, X[i]:
𝑖
1 1
𝐴[𝑖] = ∑ 𝑋[𝑗] = (𝑋[0] + 𝑋[1] + ⋯ + 𝑋[𝑖])
𝑖+1 𝑖+1
𝑗=0

10
Our first algorithm implements the formula for A[i] in a straightforward way:
ALGORITHM prefixAverages1(X[0..n-1])
//Input: an n-element array X[0..n-1]
//Output: an n-element array A[0..n-1] such that
// A[i] is the average of elements X[0],…,X[i]
for i  0 to n-1 do
sumX  0
for j  0 to i do
sumX  sumX + X[j]
A[i]  sumX /(i + 1)
return A[0..n-1]

We trace prefixAverages1 on the array X with elements (5, 7, 9, 3, 16, 14):

i j sumX X[0] X[1] X[2] X[3] X[4] X[5] A[0] A[1] A[2] A[3] A[4] A[5]
0 0 5 7 9 3 16 14
0 0 5 5 7 9 3 16 14 5
1 0 5 7 9 3 16 14 5
1 0 5 5 7 9 3 16 14 5
1 1 12 5 7 9 3 16 14 5 6
2 0 5 7 9 3 16 14 5 6
2 0 5 5 7 9 3 16 14 5 6
2 1 12 5 7 9 3 16 14 5 6
2 2 21 5 7 9 3 16 14 5 6 7
3 0 5 7 9 3 16 14 5 6 7
3 0 5 5 7 9 3 16 14 5 6 7
3 1 12 5 7 9 3 16 14 5 6 7
3 2 21 5 7 9 3 16 14 5 6 7
3 3 24 5 7 9 3 16 14 5 6 7 6
4 0 5 7 9 3 16 14 5 6 7 6
4 0 5 5 7 9 3 16 14 5 6 7 6
4 1 12 5 7 9 3 16 14 5 6 7 6
4 2 21 5 7 9 3 16 14 5 6 7 6
4 3 24 5 7 9 3 16 14 5 6 7 6
4 4 40 5 7 9 3 16 14 5 6 7 6 8
5 0 5 7 9 3 16 14 5 6 7 6 8
5 0 5 5 7 9 3 16 14 5 6 7 6 8
5 1 12 5 7 9 3 16 14 5 6 7 6 8
5 2 21 5 7 9 3 16 14 5 6 7 6 8
5 3 24 5 7 9 3 16 14 5 6 7 6 8
5 4 40 5 7 9 3 16 14 5 6 7 6 8
5 5 54 5 7 9 3 16 14 5 6 7 6 8 9

11
 (i) What are the algorithm’s basic operations?

(ii) How many times are the basic operations executed?

(iii) Determine the class O(?) the algorithm belongs to.

Our second algorithm uses the property that the formulae for A[i-1] and A[i] contain a
common term:
1
𝐴[𝑖 − 1] = 𝑖 (𝑋[0] + 𝑋[1] + ⋯ + 𝑋[𝑖 − 1])
1
𝐴[𝑖] = (𝑋[0] + 𝑋[1] + ⋯ + 𝑋[𝑖 − 1] + 𝑋[𝑖])
𝑖+1

We keep record of that common term and update it at the end of each iteration.

ALGORITHM prefixAverages2(X[0..n-1])
//Input: an n-element array X[0..n-1]
//Output: an n-element array A[0..n-1] such that
// A[i] is the average of elements X[0],…,X[i]
sumX  0
for i  0 to n-1 do
sumX  sumX + X[i]
A[i]  sumX /(i + 1)
return A[0..n-1]
We trace prefixAverages2 on the same array X with elements (5, 7, 9, 3, 16, 14):
i sumX X[0] X[1] X[2] X[3] X[4] X[5] A[0] A[1] A[2] A[3] A[4] A[5]
0 5 7 9 3 16 14
0 5 5 7 9 3 16 14 5
1 12 5 7 9 3 16 14 5 6
2 21 5 7 9 3 16 14 5 6 7
3 24 5 7 9 3 16 14 5 6 7 6
4 40 5 7 9 3 16 14 5 6 7 6 8
5 54 5 7 9 3 16 14 5 6 7 6 8 9
(i) What are the algorithm’s basic operations?

(ii) How many times are the basic operations executed?

(iii) Determine the class O(?) the algorithm belongs to.

Conclusion: for large n, prefixAverages__ is faster than prefixAverages__.

12
We can simplify analysis of algorithms:
- Determine the number of times the basic operations are performed (in the worst case)
for an instance of size n.
- Consider a dominating term in an algorithm’s growth-rate function. The low-order
terms can be ignored. If the basic operation is performed n3 + 4n2+3n times, the class
of the algorithm is O(n3).
- Ignore a multiplicative constant in the algorithm’s growth-rate function. If the basic
operation is performed 5n2 times, the class of the algorithm is O(n2).
Conclusions:
- Both time and space efficiencies are measured as functions of the algorithm input size.
- Time efficiency is measured by counting the number of times the algorithm’s basic
operations are executed.
- Different algorithms solving the same problem may have different efficiencies. For such
algorithms, we need to distinguish between the worst-case, best-case and average-case
efficiencies.
- The most important characteristic of the algorithm is the order of growth of the
algorithm’s running time.

4. Logarithmic Loops
The logarithm to the base b of x, denoted by logb x, is the exponent to which b must be
raised in order to obtain x:
𝑏 𝑘 = 𝑥  𝑘 = log 𝑏 𝑥.
Here we assume that x and b are positive real numbers and b1.
For example, log 2 8 = 3 since 23 = 8,
log 2 1 = 0 since 20 = 8.

Two typical examples of the loops which have logarithmic time complexity involve
multiplying the control variable by 2 or dividing the control variable by 2.

i  1 i  n
while i < n do while i > 1 do
application code application code
i  i*2 i  i/2

For the analysis, assume n=2k. This implies k=log2n.

Iteration Cond. to Value of i Value of i Iteration Cond. to Value of i Value of i

continue (at the (at the end of continue (at the (at the end of
the loop beginning of iteration) the loop beginning of iteration)
i<n iteration) i>1 iteration)
1 T 1 2 1 T n n/2
2 T 2 4 2 T n/2 n/4
3 T 4 8 3 T n/4 n/8
4 T 8 16 4 T n/8 n/16
     
k T 2k-1 2k = n k T n/2k-1 n/2k =1
k+1 F k+1 F

13
The algorithm with ii*2 The algorithm with ii/2
stops when condition i<n is no longer satisfied. stops when condition i>1 is no longer satisfied.
This happens when at iteration k variable i This happens when at iteration k variable i
reaches n=2k (next iteration is not performed). reaches n/2k =1 (next iteration is not performed).

Thus the number of iterations is k=log2n. Thus the number of iterations is k=log2n.

The analysis of the general case, when 2k-1 < n ≤ 2k, is similar. Notice that 𝒌 = ⌈𝐥𝐨𝐠𝟐 𝒏⌉.
The algorithm with ii*2 The algorithm with ii/2
stops when condition i<n is no longer satisfied. stops when condition i>1 is no longer satisfied.
This happens when at iteration k variable i This happens when at iteration k variable i
reaches i=2k ≥ n, violating condition i<n reaches i=n/2k ≤ 1, violating the condition i>1
for the first time. for the first time.

Example 1. Find the number of digits in the binary representation of a given positive
decimal integer n.
Recall that the digits of the binary representation akak-1…a1a0 of a decimal number n satisfy
𝑛 = 𝑎𝑘 ∙ 2𝑘 + 𝑎𝑘−1 ∙ 2𝑘−1 + ⋯ + 𝑎1 ∙ 2 + 𝑎0 , where 𝑎𝑘 ≠ 0.

ALGORITHM number-of-binary-digits(n)
//Input: A positive decimal integer n
//Output: The number of binary digits in the
// binary representation of n
count  1
while n > 1 do
count  count+1
n  n/2
return count

Tracing for n=13: n n n n

Iteration (at the start of count (at the end of Iteration (at the start of count (a
iteration) iteration) iteration) ite
1 1
1 1
2 2
3 3
4 4
For the input n=13, the algorithm
ALGORITHM returns ___
number-of-binary-digits(n)
//Input: A positive decimal integer n
As we have seen, if the control variable is halved, then the number of iterations is k=log2n.
//Output: The number of binary digits in the
In Example 1 the
//control variable is halved
binary and rounded down
representation of (nn  n/2). This implies
that the numbercount
of iterations
 1 is bounded by k=log2n.
(i) while
What are n > 1 do
the algorithm’s basic operations?
count  count+1
(ii) How many times n aren/2
they repeated?
return count
(iii) Determine the class O(?) the algorithm belongs to.

14
Correctness proof: The algorithm counts how many times operation n/2 is done before
reaching n≤1. With the initial value count=1, it returns the number of divisions plus 1.
Consider 𝑛 = 𝑎𝑘 ∙ 2𝑘 + 𝑎𝑘−1 ∙ 2𝑘−1 + ⋯ + 𝑎2 ∙ 22 + 𝑎1 ∙ 2 + 𝑎0
The first division results in 𝑛 = 𝑎𝑘 ∙ 2𝑘−1 + 𝑎𝑘−1 ∙ 2𝑘−2 + ⋯ + 𝑎2 ∙ 2 + 𝑎1
The second division results in 𝑛 = 𝑎𝑘 ∙ 2𝑘−2 + 𝑎𝑘−1 ∙ 2𝑘−3 + ⋯ + 𝑎2
…
After k divisions 𝑛 = 𝑎𝑘 = 1 (the first digit of the binary representation),
and count=k+1 (the number of binary digits). 

5. Basic Principles of Complexity Analysis

The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n.

Algorithm equalMatrices: ____ comparisons are done if ___________________

The worst-case analysis is our main subject.

The best-case efficiency of an algorithm is its efficiency for the best-case input of size n.
Algorithm equalMatrices: ____ comparisons are done if ___________________
The best-case analysis is only useful for special instances.

The average-case efficiency of an algorithm is its efficiency for a “typical” or “random”

input of size n.
The average-case analysis is more complicated than the worst-case analysis and it is beyond
the scope of this module.

Suppose algorithm A performs g(n) basic cf(n) g(n)

operations for worst-case instances of size
n. does
The time complexity of Algorithm A is of not
order f(n) - denoted O(f(n)) - if there exist matter
positive constants c and n0 such that A
requires no more than cf(n) operations to
solve a problem of size
n  n0, n
n0
i.e., g(n) ≤ cf(n) for n  n0.

O-notation (“big-O”) is used to express asymptotic upper bound for a given function f(n), i.e.,
to give an upper bound to within a constant factor.

15
 5.1 Formal Definition of Big-O
cf(n) g(n)

To prove that g(n) is O(f(n)) we need to does

specify two positive constants c and n0 such not
that matter
g(n) ≤ cf(n) for any n  n0.

n
n0
Examples
1. Suppose an algorithm performs g(n) = n+3 basic operations.
Step 1: the dominating term in g(n) = n+3 is “n”; the low-order term “3” should be
ignored. Thus we need to prove that g(n) = n+3 is O(n).
Step 2: in accordance with the definition of big-O we need to show that there exist
positive constants c and n0 such that n+3  cn for all n  n0.
Consider inequalities n n for any n, including n 1,
3 3n for n 1.
Their sum gives n+3  4n for n 1.
Thus the definition of O(n) holds with c=4 and n0=1.
Notice that the choice of c and n0 is not unique. Prove that n+3  2n for all n  3.

2. Suppose an algorithm performs g(n) = 2n2+2n basic operations.

Step 1: the dominating term in g(n) = 2n2+2n is “2n2”; the low-order term “2n” should
be ignored. We should also ignore the multiplicative constant in “2n2”. Thus we need to
prove that g(n) = 2n2+2n is O(n2).
Step 2: in accordance with the definition of big-O we need to show that there exist
positive constants c and n0 such that 2n2+2n  cn2 for all n  n0.
Consider inequalities 2n2  2n2 for any n, including n 1,
2n  2n2 for n 1.
Their sum gives 2n2+2n  4n2 for n 1.
Thus the definition of O(n2) holds with c=4 and n0=1.

3. Suppose an algorithm performs 𝑔(𝑛) = 3 log 2 𝑛 + 2𝑛 basic operations.

Step 1: the dominating term in 𝑔(𝑛) = 3 log 2 𝑛 + 2𝑛 is “2n”; the low-order term
“3 log 2 𝑛” should be ignored. We should also ignore the multiplicative constant in “2n”.
Thus we need to prove that 3 log 2 𝑛 is O(n).
Step 2: in accordance with the definition of big-O we need to show that there exist
positive constants c and n0 such that 3 log 2 𝑛 + 2𝑛  cn for all n  n0.
Consider inequalities log 2 𝑛  n for any n>0, including n 1,
2n  2n for any n, including n 1.
Multiplying the first inequality by 3 and adding the two inequalities we obtain
3 log 2 𝑛 + 2𝑛  5n for n 1.
Thus the definition of O(𝑛) holds with c=5 and n0=1.

16
4. Suppose an algorithm performs g(n) = 1000 basic operations for any input of size n.
We prove that g(n) = 1000 is O(1).
Indeed, 1000≤10001 for any n, including n 1.
Thus the definition of O(1) holds with c=1000 and n0=1.

For each expression 5a)-5h) define the big-O class and present a formal proof.
You can use the templates on pages 19-21.
5a) 100n + 5

5b) 2n2 + 5n

5c) 5n3 - 2n

5d) 6 log2n + 3n

5e) 3n4 + n log2n

5f) 2100

5g) 5n2+n3/2

5h) 3n + 5nlog2n 1

1Notice that log2n≥1 for n≥2. Multiplying both parts of the inequality “log2n≥1” by n and
assuming n≥2 (a positive value), we obtain: nlog2n≥n for n≥2.
17
Proving that __100n + 5____ is O(n)
In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that 100n + 5  cn for all n  n0.
Indeed,
100n  100n for any n, including n1,
(provide a
5  5n for any n 1. justification
and specify
c and n0)

Thus 100n + 5  105n for n1 (c=_105; n0=_1).

Proving that ___________ is O( )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that ____  c for all n  n0.
Indeed,
(provide a
justification
and specify
c and n0)

Thus _____  for n _ __ (c=_ __ ; n0=_ __).

Proving that ______________ is O( )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that _____  c for all n  n0.
Indeed,

(provide a
justification
and specify
c and n0)

Thus _____  for n ___ (c=____ ; n0=___).

18
Proving that ______________ is O(__ )
In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that __  c for all n  n0.
Indeed,

(provide a
justification
and specify
c and n0)

Thus ___  for n _____ (c=______ ; n0=___).

Proving that ______________ is O( __ )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that ___  c for all n  n0.
Indeed,
(provide a
justification
and specify
c and n0)

Thus ___  for n ______ (c=______ ; n0=___).

Proving that ______________ is O( __ )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that __  c for all n  n0.
Indeed,

(provide a
justification
and specify
c and n0)

Thus __  for n _____ (c=_____ ; n0=___).

19
Proving that ______________ is O( )
In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that ___  c for all n  n0.
Indeed,

(provide a
justification
and specify
c and n0)

Thus ___  for n ___ (c=_____ ; n0=___).

Proving that ______________ is O( )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that ___  c for all n  n0.
Indeed,
(provide a
justification
and specify
c and n0)

Thus __  for n _____ (c=___ ; n0=___).

Proving that ______________ is O( )

In accordance with the definition of big-O we need to show that there exist positive
constants c and n0 such that ___  c for all n  n0.
Indeed,

(provide a
justification
and specify
c and n0)

Thus ___  for n ___ (c=_____ ; n0=___).

20
In the computing literature the base 2 of the logarithm is usually omitted.
We write O(logn) instead of (log2 𝑛),
O(nlogn) instead of 𝑂(𝑛 log2 𝑛)
since the logarithm in any base is proportionate to a base-2 logarithm.
For example, let us demonstrate that 𝑔(𝑛) = log10 𝑛 is 𝑂(log2 𝑛).
Indeed, log10 𝑛 = log10 2 × log 2 𝑛 ≤ 0.302 × log 2 𝑛 for any n≥1.
The formula
log 𝑏 𝑛 = log 𝑏 𝑎 ∙ log 𝑎 𝑛
makes it possible to switch from one base to another, leaving the expression logarithmic but
with a new multiplicative constant (log 𝑏 𝑎).

The formal definition of big-O explains why we can simplify analysis of algorithms:
• Determine the number of times the basic operations are performed (in the worst case)
for an instance of size n.
• Consider a dominating term in an algorithm’s growth-rate function. The low-order
terms can be ignored. If the basic operation is performed n3 + 4n2+3n times, the class of
the algorithm is O(n3).
• Ignore a multiplicative constant in the algorithm’s growth-rate function. If the basic
operation is performed 5n2, the class of the algorithm is O(n2).

5.2 Properties of Big-O

Consider an algorithm that operates on an array of n elements. Suppose the most frequent
operation of that algorithm is multiplication and it is repeated 5n3 times. There are a
number of other operations as well:
- summation, which is repeated 3n2 times,
- comparison, repeated 4n times,
- division, repeated twice.
We prove formally that the time complexity of the algorithm is O(n3), so that it is sufficient
to count the number of repetitions of the most frequent operation.

Indeed, the total number of basic operations is 5n3 + 3n2 + 4n + 2, and it is bounded by 14n3
for n≥1:
5n3 + 3n2 + 4n + 2 ≤ 5n3 + 3n3 + 4n3 + 2n3= 14n3.
Here we use:
5n3 ≤ 5n3 for n≥1,
3n2 ≤ 3n3 for n≥1,
4n ≤ 4n3 for n≥1,
2 ≤ 2n3 for n≥1.
Thus the time complexity is O(n3), where in the definition of big-O, c=14 and n0=1.

A general result: if the most frequent operation of an algorithm is repeated at most 𝑐1 𝑛𝑘

times for any array of size 𝑛 ≥ 1, and there are 𝑐2 other operations, each performed less
frequently than the main operation, then the time complexity of the algorithm is 𝑂(𝑛𝑘 ).
Here 𝑘, 𝑐1 and 𝑐2 are some positive integers.

Proof: The total number of basic operations is no more than

𝑐1 𝑛𝑘 + 𝑐2 × (𝑐1 𝑛𝑘 ) = (𝑐1 + 𝑐2 𝑐1 )𝑛𝑘 .
Thus the time complexity is 𝑂(𝑛𝑘 ), where in the definition of big-O, 𝑐 = 𝑐1 + 𝑐2 𝑐1 and 𝑛0 = 1. 

21
1. A single assignment statement is usually O(1), since its execution time is not
dependent on the amount of data.
2. In an if/else statement, the test is usually O(1). Only one of the conditional
statements is executed and we analyse the running time of the most time-consuming
conditional statement (worst case).
3. If an algorithm consists of two stages,
- Stage 1 of time complexity O(n),
- Stage 2 of time complexity O(n2),
then the overall time complexity of the algorithm is O(n2).
4. In general, if an algorithm consists of two stages,
- Stage 1 of time complexity O(f1(n)),
- Stage 2 of time complexity O(f2(n)),
then the overall time complexity of the algorithm is O(max{f1(n), f2(n)}).
Proof of Property 3.
Since Stage 1 is of time complexity O(n), then by the formal big-O definition there exist two
positive constants c1 and n1 such that the number of basic operations of Stage 1 is bounded
by c1n for any n≥n1. Notice that n1≥1.
Similarly, since Stage 2 is of time complexity O(n2), then by the formal big-O definition there
exist two positive constants c2 and n2 such that the number of basic operations of Stage 2 is
bounded by c2n2 for any n≥n2. Notice that n2≥1.
Let n0=max{n1,n2}. Clearly, n0≥1. Then
Stage 1 incurs at most c1n basic operations for any n≥n0,
Stage 2 incurs at most c2n2 basic operations for any n≥n0.
Since and c1n ≤ c1n2 for n≥n0, then both stages incur at most c1n + c2n2 ≤ c1n2 + c2n2 = (c1+c2)n2
basic operations for any n≥n0.
Thus the overall time complexity of the algorithm is O(n2), with constants
c= c1+c2,
n0=max{n1,n2}
in the formal definition of Big-O. 
Property 4 can be proved similarly.

5.3 Efficiency classes

The basic efficiency classes and algorithm examples are listed in the table below, in
increasing order of their order of growth.

Class Name Examples

O(1) constant finding the minimum value in an ordered array
O(log n) logarithmic binary search
polynomial

O(n) linear sequential search

O(n log n) linear advanced sorting
logarithmic
O(n2) quadratic elementary sorting
O(n3) cubic matrix multiplication
O(2n) exponential combinatorial problems
polyno
non-

mial

O(n!) factorial combinatorial problems

22
Algorithms that require an exponential number of operations are practical for solving only
problems of very small size.
Exponential growth is characterized by doubling, and a few doublings can lead quickly to
enormous numbers.

The figure below illustrates the rates of growth of various functions.

7n2
3000 3n 0.8n3
100n

2000 400√𝑛 = 400n½

300log2n

1000

7
0
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36

The order of the rates of growth is as follows: 7

7, 300log2n, 400√𝑛, 100n, 7n2, 0.8n3, 3n
1
𝑂(1), 𝑂(log2 𝑛), 𝑂(√𝑛) = 𝑂 (𝑛2 ) O(n), O(n2), O(n3), O(3n)

Notice that
- 2n and n! grow so fast, that their values become astronomically large even for small
values of n.
- It takes longer than the estimated age of the planet Earth to execute 2100 operations
for a computer performing one trillion (1012) operations per second.
On the other hand,
- Logarithmic function has a slow rate of growth.
- The program implementing an 𝑂(log 𝑛)-time algorithm runs almost instantaneously
even on large inputs.

23
 1 logn n nlogn n^2 n^3 2^n
1 0.0 1 0.0 1 1 2
1 1.0 2 2.0 4 8 4
1 2.3 5 11.6 25 125 32
1 3.3 10 33.2 100 1000 1024
1 3.9 15 58.6 225 3375 32768
1 4.3 20 86.4 400 8000 1048576
1 4.9 30 147.2 900 27000 1073741824
1 5.3 40 212.9 1600 64000 1099511627776
1 5.6 50 282.2 2500 125000 1125899906842620
1 5.9 60 354.4 3600 216000 1152921504606850000
1 6.1 70 429.0 4900 343000 1180591620717410000000
1 6.3 80 505.8 6400 512000 1208925819614630000000000
1 6.5 90 584.3 8100 729000 1237940039285380000000000000
1 6.6 100 664.4 10000 1000000 1267650600228230000000000000000

polynomial-time algorithms exponential-time algorithms

Follow-up reading
Millennium Problems: http://www.claymath.org/millennium-problems

Suppose algorithms A1, A2, …, A6 solve the same problem on an input consisting of n
numbers. The number of steps (basic operations) performed by each algorithm is given in
the second column of the table below.

Suppose a computer performs 1 million operations per second.

The entries in columns 3-6 specify the largest size n of a problem that can be solved by the
corresponding algorithm in 1 second, 1 hour, 1 month, 1 century.

Algorithm Running 1 second 1 hour 1 month 1 century

time
A1 log2n 10300000 101000000000 10800000000000 10900000000000000
A2 n 106 3.6109 2.61012 3.111015
A3 n2 1,000 6104 1.6106 5.5107
A4 n3 100 1,532 13,736 145,972
A5 2n 19 31 41 51
A6 n! 9 12 15 17

To summarise, we conclude that the Big-O analysis provides a formal, universal technique
for comparing algorithms.

24
 6. Sorting: iterative algorithms
Sorting is one of the most frequently performed computing tasks.

- It is often required to keep data in order.

- Sorting makes many questions about an array easier to answer. In a sorted array,
searching can be done efficiently (dictionaries, telephone books, class lists are sorted).
- Often, sorting is required as an auxiliary step for more complex algorithms.
Sorting has been studied intensively and many algorithms have been developed. Simple but
relatively slow algorithms require O(n2) time. More advanced algorithms require O(nlogn)
time in the worst case.
6.1 Selection Sort
We start with a straightforward algorithm called Selection Sort. For simplicity, we assume
that the data items are numbers and they should be sequenced in the ascending order.
An array A[0..n-1] of n elements A[0], A[1], … , A[n-1] is sequenced in ascending order if
A[0]  A[1]  A[2]  …  A[n-1].
The general idea of the algorithm:
- search the array for the smallest element and swap that element with the first one;
- search for the second smallest and swap that element with the second one;
- repeat the described steps until the whole array is sorted.

ALGORITHM selectionSort(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: array A[0..n-1] sorted in ascending order
for i  0 to n-2 do
find the smallest element A[mini] among A[i],A[i+1],…,A[n-1]
swap A[i] and A[mini]

To find the smallest element A[mini] among A[i], A[i+1], … A[n-1], we start
with mini equal to the index of the first element i. Then we look down the array, and if
we find an element A[j] smaller than A[mini], then we store the index of that
element: minij. The process is repeated until we get to the end of the array.
mini  i
for j  i+1 to n-1 do
if A[j] < A[mini] mini  j

The value of i determines whether we are searching for the smallest element (i=0), the
second smallest (i=1), etc.
To swap two elements A[i] and A[mini] we need a temporary variable tmp:
tmp  A[i]
A[i]  A[mini]
A[mini]  tmp

25
Combining the algorithm above with the fragments for finding the smallest element in the
sub-array and swapping A[i] and A[mini] we obtain:
ALGORITHM selectionSort(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: array A[0..n-1]sorted in ascending order
for i  0 to n-2 do
//find the smallest element A[mini] among A[i], A[i+1],…,A[n-1]
mini  i
for j  i+1 to n-1 do
if A[j] < A[mini] mini  j
//swap A[i] and A[mini]
tmp  A[i]
A[i]  A[mini]
A[mini]  tmp

Let us trace the algorithm through the array of n=6 numbers (89, 45, 68, 90, 34, 17).

26
 A[5]=
A[0] A[1] A[2] A[3] A[4]
i j A[n-1] mini

find the smallest element

among A[0], A[1], …, A[5]
0 89 45 68 90 34 17 0
0 1 89 45 68 90 34 17 1
i=0:
0 2 89 45 68 90 34 17 1 n-1 comparisons
0 3 89 45 68 90 34 17 1 at most n assignments

0 4 89 45 68 90 34 17 4
0 5 89 45 68 90 34 17 5
0 5 17 45 68 90 34 89 5 3 assignments to swap A[i] and A[mini]

find the smallest element

1 17 45 68 90 34 89 1

among A[1],…, A[5]

1 2 17 45 68 90 34 89 1 i=1:
n-2 comparisons
1 3 17 45 68 90 34 89 1 at most n-1 assignments
1 4 17 45 68 90 34 89 4
1 5 17 45 68 90 34 89 4
3 assignments to swap A[i] and A[mini]
1 5 17 34 68 90 45 89 4

among A[2],…, A[5]

2 17 34 68 90 45 89 2 i=2:

find the smallest

n-3 comparisons
2 3 17 34 68 90 45 89 2 at most n-2 assignments
2 4 17 34 68 90 45 89 4
2 5 17 34 68 90 45 89 4
3 assignments to swap A[i] and A[mini]
2 5 17 34 45 90 68 89 4
among A[3],…,A[5]

3 17 34 45 90 68 89 3
smallest

3 4 17 34 45 90 68 89 4
3 5 17 34 45 90 68 89 4
3 5 17 34 45 68 90 89 4 3 assignments to swap A[i] and A[mini]
i=n-2:
A[4],A[5]

4 17 34 45 68 90 89 4
smallest

1 comparison
4 5 17 34 45 68 90 89 5 at most 2 assignments
4 5 17 34 45 68 89 90 5 3 assignments to swap A[i] and A[mini]

Complexity Analysis: Version 1

Finding the smallest element:
The number of comparisons is (n -1) + (n -2) + … + 2 + 1 = ½ n(n-1)
The number of assignments is no larger than n + (n - 1) + (n -2) + … + 2 = ½ n(n+1) – 1

Swapping two elements:

To swap two elements, three assignments should be made. Swapping is performed for
i=0,1,…,n-2, i.e., n-1 times. Hence there are 3(n-1) assignments.

In total we need at most ½n(n-1) + ½n(n+1) –1 + 3(n-1)= n2 + 3n - 4 comparisons and

assignments, i.e., the time complexity of the selection sort is O(n2).

27
Complexity Analysis: Version 2
The analysis can be simplified using the result discussed on p. 22: it is sufficient to identify
the most frequent operation and count the number of times it is repeated.
In selection sort, the most frequent operation is comparison A[j]<A[mini].
There are two nested loops.
- The outer loop is executed for each value i=0, 1, …, n-2.
- For each value of i, the comparison A[j]<A[mini] of the inner loop is executed:

i=0 j=1
j=2
 n-1 times
j=n-1
i=1 j=2
 n-2 times
j=n-1
  
i=n-3 j=n-2
j=n-1 2 times
i=n-2 i=n-1 1 time
Thus the comparison A[j]<A[mini] is executed (n -1)+…+2+1 = ½ n(n-1) times, and the
running time of selection sort is O(n2).

Proof of Correctness of Selection Sort.

- The array at any moment is divided into two parts: sorted and unsorted, and any element
of the sorted sub-array is less than or equal to any element of the unsorted one.
- In each pass of the algorithm, the minimum element of the unsorted sub-array is found
and swapped with the first element of the unsorted sub-array. The sorted sub-array is
thus extended by one element in every pass.
For a formal proof, consider the outer loop controlled by i. We formulate a property, which
holds at each iteration (a so-called loop invariant)
At the beginning of iteration i, the sub-array A[0..i-1] is sorted and any element in A[0..i-1]
is less than or equal to any element in A[i..n-1].

The correctness of the algorithm can now be proved by induction.

1) The invariant is true initially: the sub-array A[0. . -1] is empty.
2) If the invariant is true for i=k, it is true for i=k+1.
Indeed the sorted sub-array is appended at the end by a larger element (or by an
element equal). That element is also less than or equal to the remaining elements.
3) When the loop terminates, the invariant is true for the entire array.
4) The loop does terminate.

28
 6.2 Bubble Sort

ALGORITHM bubbleSort(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: array A[0..n-1] sorted in ascending order
for i  0 to n-2 do
for j  0 to n-2-i do
if A[j]>A[j+1]
tmp  A[j]
A[j]  A[j+1]
A[j+1]  tmp
Tracing, analysis and correctness proof is left as an exercise.

6.3 Insertion Sort

ALGORITHM insertionSort(A[0..n-1])
//Input: an array A[0..n-1] of n numbers
//Output: array A[0..n-1] in ascending order
for i  1 to n-1 do
tmp  A[i]
j i-1
while (j≥0 and tmp < A[j]) do
A[j+1]  A[j]
j  j-1
A[j+1]  tmp

Tracing, analysis and correctness proof is left as an exercise.

Brute Force Approach

Selection sort is an example of the brute-force strategy. It is simple and straightforward. As
a rule, the brute-force technique is directly based on the problem’s statement.

The brute-force technique can be applied to a wide range of problems. However, for some
problems faster algorithms can be developed using the divide-and-conquer approach.

29
 7. Search Algorithms
Consider the problem of searching an array of n elements to find an element with a
particular value K (the search key). There are two basic approaches:
- sequential search that requires O(n) time;
- binary search that requires O(logn) time.
Binary search is much faster than sequential search, but it works only on sorted arrays.

7.1 Sequential Search

The algorithm begins at the first element in the array and looks at each element in turn until
K is found or the end of the array is reached.
ALGORITHM sequentialSearch(A[0..n-1],K)
// Input: an array A[0..n-1] and a search key K
// Output: the index of the element of A that matches K,
// or –1, if there is no such element
i  0
while i  n-1 and A[i]K do
i  i+1
if i < n return i // i is the index of key K
else return -1 // key K is not found

The worst case happens if ____________________________

The time complexity of sequential search is O(n) since in the worst case the algorithm
performs _______ comparisons.
Observe, that in the best case, one comparison is done (if key K is the first element).
On average, n/2 comparisons are done.

7.2 Binary Search

Binary search is based on using the famous divide-and-conquer technique, which consists of
the following three mains steps.
1. Divide: if a stopping criterion is not reached, then a problem’s instance is divided into
smaller instances.
2. Recur: the smaller instances are solved recursively.
3. Conquer: if necessary, the solutions obtained for the smaller instances are combined in
order to get a solution to the original problem.
These ideas can be successfully applied to the search problem. Suppose the array is
sequenced in ascending order. Then the main steps of divide-and-conquer can be
described as follows.
1. Divide: if an array is non-empty and the middle element is not equal to K, then divide the
array into two sub-arrays about half as large. If K is smaller than the middle element,
choose the left sub-array. If K is larger, choose the right sub-array.
2. Recur: apply the same method to solve a smaller instance, i.e., to search a sub-array to
find K.
3. Conquer: since only one half of the array is considered in each step and the other half is
discarded, there is no need to combine the solutions.

30
ALGORITHM binarySearch(A[l..r],K)
//The algorithm implements iterative binary search
//Input: an array A[l..r] sorted in ascending order, defined
// by its left and right indices l and r;
// a search key K
//Output: an index of the array’s element that is equal to K,
// or –1 if there is no such element
while l  r do
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] r  mid-1
else l  mid+1
return –1 //Search key not in array

If at some stage we consider a part of array with indices l, l+1, , r, then the index of
the middle element is found as (l+r)/2, which is the largest integer smaller than or
equal to (l+r)/2 (the result of rounding (l+r)/2 down, with the fractional part
discarded).
For example,
- if we have an array of 13 elements with left and right indices l=0, r=12, then
(l+r)/2 = (0+12)/2 = 6.
- if we have an array of 12 elements with left and right indices l=0, r=11, then
(l+r)/2 = (0+11)/2 = 5.
Example.
Consider an array of 13 elements and search key K=19. The operation of binary search is
illustrated in the figure below.
index l=0 1 2 3 4 5 6 7 8 9 10 11 r=12
value 11 12 13 16 19 20 25 27 30 35 39 41 46

Compare K with 25
Choose left sub-array
because K < 25

index l=0 1 2 3 4 r=5

value 11 12 13 16 19 20

Compare K with 13 Choose right sub-array

because K > 13

index l=3 4 r=5

value 16 19 20

The search key is found.

Compare K with 19 Return its index 4.
31
In-class exercise: Fill in the tracing table
l r mid K == A[mid]? (true/false) K < A[mid]? (true/false)
0 12

7.3 Analysis of Binary Search

In each iteration binary search discards no less than one half of the array by comparing the
search key with the middle element. To estimate the number of iterations, suppose first that
n is a power of 2, i.e.,
𝑛 = 2𝑞 (1)
for some q.
The search requires the following steps:
- inspect the middle element of an array of size n;
𝑛
- inspect the middle element of an array of size at most 2 ;
𝑛
- inspect the middle element of an array of size at most 22 , and so on.
If we divide an array of n elements in half, then divide one of those halves in half, and
continue dividing halves until only one element remains, we perform q divisions (because
𝑛
2𝑞
= 1 according to our assumption (1)).
Thus in the worst case the algorithm performs at most q iterations and, therefore, at most q
comparisons (considering K==A[mid] as the most frequent operation). Due to (1),
q = log2n.
It means that the time complexity of the algorithm is O(logn) in the worst case.

Suppose now that n is not necessarily a power of 2. We can always find an integer q such
that
2𝑞−1 ≤ 𝑛 < 2𝑞 .
Notice that
q –1 ≤ log2n < q,
q ≤ log2n +1. (2)
The algorithm still performs no more than q iterations to obtain a sub-array with one
element (at most q iterations are done if the number of elements is 2𝑞 ; in our case we have
less than 2𝑞 elements).
Using (2) we conclude that the algorithm is O(logn).

The time complexity of the binary search algorithm is O(logn).

Binary search is much faster than sequential search. For example, log21,000,000 = 19. This
means that sequential search over an array of one million sorted elements may perform one
million comparisons while binary search performs no more than 20 comparisons. For large
arrays, binary search has a huge advantage over sequential search.
However, binary search requires an array to be sorted, which incurs overheads.

32
 8. Recursive Algorithms
There are two approaches to writing repetitive algorithms: iteration and recursion.
- Iteration involves loops (while-loops, for-loops)
- Recursion is a repetitive process in which an algorithm calls itself.

Recursion solves a problem by solving a smaller instance of the same problem.

It solves this new problem by solving an even smaller instance of the same problem.
Eventually the problem will be so small that its solution will be obvious.

Every recursive call must either solve a part of the problem or reduce the size of the
problem. Thus a recursive algorithm should have two parts:
- base case, which handles a small input directly without recursion;
- recursive part, which contains one or more recursive calls.

8.1 Calculating n!
We start with a popular example, which is often used to introduce recursive algorithms.
Consider calculation of the factorial function n! defined as
if n = 0,
Factorial ( n ) = 
1,
1  2  3  ...  (n − 1)  n, if n  1.


Iterative formula: Recursive formula:

Factorial(0) = 1
0! = 1,
Factorial(n) = Factorial(n-1)  n
n! = 12  …  n for n1
Iterative Recursive algorithm
algorithm
ALGORITHM iterativeFactorial(n) ALGORITHM Factorial(n)
//Computes n! iteratively //Computes n! recursively
//Input: a nonnegative integer n //Input: a nonnegative integer n
//Output: The value of n! //Output: The value of n!
if n==0 return 1 if n==0 return 1
product  1 else return Factorial(n-1)*n
for i  1 to n do
product  product * i
return product Box-tracing for n=3 (recursive algorithm):

Factorial(3) Factorial(4)
Tracing table for n=3 (iterative algorithm): return 23=6

i product Factorial(2) Factorial(2)

1 return 12=2

1 11=1
Factorial(1) Factorial(1)
2 12=2 return 11=1
3 23=6
Factorial(0) Factorial(0)
For n=3, both algorithms compute 6=3! return 1
33
In a recursive algorithm, when the current module calls a subroutine, it suspends
processing and the called subroutine takes over control of the program.
When the subroutine completes its processing and returns to the module that called it, the
module wakes up and continues processing.
Recursive algorithms are often quite elegant, but complexity analyses of a recursive
algorithm takes a bit of additional work. Below we present two methods for complexity
analysis.

Method 1 is the same as we considered for iterative algorithms

1) What is the algorithm’s main operation?
Iterative Algorithm to calculate n! Recursive Algorithm to calculate n!

2) How many times is the main operation executed?

Iterative Algorithm to calculate n! Recursive Algorithm to calculate n!

3) What is the class O(…) the algorithm belongs to?

Iterative Algorithm to calculate n! Recursive Algorithm to calculate n!
O(…) O(…)

Method 2 is the special method for analyzing recursive algorithms. It requires formulating a
recurrence relation and solving it.
1) Determine the algorithm’s main operation
In the recursive algorithm Factorial(n), the main operation is multiplication.
2) Set up a recurrence relation with initial condition
Let M(n) denote the number of multiplication performed by Factorial(n).
M(n) = M(n-1) + 1 for n>0

multiplications multiplications to multiply

to compute to compute Factorial(n-1)
Factorial(n) Factorial(n-1) by n
M(0) = 0 (no multiplications if n=0)
3) Solve the recurrence or estimate the rate of growth of its solution
One way for solving a recurrence relation is the method of backward substitution.
Given: M(n) = M(n-1) + 1 for n>0,
M(0) = 0.
Solution: M(n) = M(n-1) +1 (substitute M(n-1) = M(n-2) + 1)
= [M(n-2) + 1] +1
= M(n-2) +2 (substitute M(n-2) = M(n-3) + 1)
= [M(n-3) + 1] + 2 = M(n-3) + 3.
After several substitutions we can make a guess: M(n) = M(n-i) + i for 0 ≤ i ≤ n.
The correctness of this formula can be proved by mathematical induction.
Substituting i=n we obtain:
M(n) = M(n-1) + 1 = … = M(n-i) + i = … = M(n-n) + n = 0+n = n.
Conclusion: Recursive algorithm Factorial(n) performs n multiplications. Thus it is O(n).

34
 8.2 Recursive Version of Binary Search
The base case of the recursive binary search algorithm can be formulated as follows:
if there are no elements to search, return -1
Formally, the above condition can be stated as “l>r” (notice that if l≤r, then there is at
least one element in the array).
The recursive part implies the search over a half of the array. If the search key is in the
array, the algorithm uses smaller and smaller portions of the array until it finds the item. If
the search key is not in the array, the recursive calls will lead to the base case.
The recursive implementation of binary search is presented below. Observe that the
algorithm does not use a loop.

ALGORITHM binarySearch(A[l..r],K)
//The algorithm implements recursive binary search
//Input: an array A[l..r] sorted in ascending order, defined
// by its left and right indices l and r;
// a search key K
//Output: an index of the array’s element that is equal to K or
// –1 if there is no such element
if l > r return –1 //Search key not in array
else
mid  (l+r)/2
if K == A[mid] return mid
else
if K < A[mid] return binarySearch(A[l..mid-1],K)
else return binarySearch(A[mid+1..r],K)

Box-tracing of the recursive version of binary search on the array

l=0 1 2 3 4 5 6 7 8 9 10 11 r=12
11 12 13 16 19 20 25 27 30 35 39 41 46
and K=19 can be illustrated as follows.

binarySearch(A[0..12], 19) binarySearch(A[0..12], 19) The algorithm returns

Return 4 4, the index of the
found element.

binarySearch(A[0..5], 19) binarySearch(A[0..5], 19)

Return 4

binarySearch(A[3..5], 19) binarySearch(A[3..5], 19)

Return 4

Complexity analysis: Method 1 gives the same result for the recursive version of binary
search as for the iterative one. As shown below, Method 2 also proves that the algorithm is
O(logn).

35
1) Determine the algorithm’s main operation
We select K==A[mid] as the most frequent operation.
2) Set up a recurrence relation with initial condition
Let C(n) denote the number of comparisons K==A[mid] performed by the recursive
version of binary search on the array of size n, n = r–l+1.

comparisons K==A[mid] performed by

binarySearch(A[l..mid-1],K) or
binarySearch(A[mid+1..r],K)

C(n) ≤ C(n/2) + 1 for n>1

comparisons K==A[mid] performed one comparison K==A[mid] to select

by binarySearch(A[l..r],K) subarray A[l..mid-1] or A[mid+1..r]

C(1) = 1 (one comparisons if n=1)

3) Solve the recurrence or estimate the rate of growth of its solution
Given: C(n) ≤ C(n/2)+ 1 for n>0,
C(1) = 1.
Solution: Consider n=2q. This implies q=log2n.
q q
C(2 ) ≤ C(2 /2) + 1
= C(2q-1) + 1 (substitute C(2q-1) ≤ C(2q-2) + 1)
q-2
≤ [C(2 )+ 1] + 1
q-2 q-2 q-3
= C(2 ) + 2 (substitute C(2 ) ≤ C(2 ) + 1)

≤ [C(2q-3) + 1] + 2 = C(2q-3) + 3.
q q-i
After several substitutions we can make a guess: C(2 ) ≤ C(2 ) + i for 0 ≤ i ≤ q.
The correctness of this formula can be proved by mathematical induction.
Substituting i=q we obtain:
C(2q) ≤ C(2q-1) + 1 ≤ … ≤ C(2q-i) + i ≤ … ≤ C(2q-q) + q = C(1)+q = 1+ log2n.

Conclusion: Recursive implementation of binary search performs at most 1+ log2n

comparisons, the same as the iterative version.
The running time is O(logn), the same as for the iterative version.

36
 8.3 Euclid’s Algorithm to Find the Highest Common Factor
Another classical example of a recursive algorithm is finding the highest common factor
(hcf). Highest common factor of two nonnegative integers a and b, not both zero, is the
largest integer that divides both numbers. The algorithm presented here is a variation of
Euclid’s algorithm, which is based on applying repeatedly the formula:
hcf(𝑎, 𝑏) = hcf(𝑏, 𝑎 mod 𝑏)
until 𝑎 mod 𝑏 is equal to 0. Here 𝑎 mod 𝑏 is the remainder of dividing a by b.
Taking into account that hcf(𝑎, 0) = 𝑎, the complete recursive formula is as follows:

𝑎, if 𝑏 = 0,
hcf(𝑎, 𝑏) = {
hcf(𝑏, 𝑎 mod 𝑏), otherwise.

We can express this formula in the pseudocode:

ALGORITHM hcf(a,b)
//Input: two nonnegative integers a and b, not both zero
//Output: the hcf of a and b
if b == 0 return a
return hcf(b, a mod b)

(a) Present box-tracing of the algorithm for a=24, b=36.

hcf(24,36)
if b==0 return a
return hcf(b, amodb)

(b) Is the base case appropriate? (How is the problem getting smaller? Do you always
approach a base case?)
Conclusions
1. As a rule, a recursive algorithm is simpler than its iterative counterpart.
2. If you can easily, clearly, and efficiently solve a problem by an iterative algorithm, you
should do so (a recursive algorithm of the same time complexity may be slower due to
overheads related to suspending and resuming subroutines). For some problems, it is
difficult to develop an iterative algorithm. If a recursive algorithm is straightforward,
you should do so. Three Recursive Algorithms to Calculate 2𝑛

37
Three recursive algorithms to calculate 2𝑛 are presented below.
- The first algorithm (a) is an example of a poor solution to a simple problem.
- The second algorithm (b) finds the result much faster.
- The third algorithm (c) is the fastest.
1, if 𝑛 = 0,
(a) Computing 2𝑛 can be done recursively using the formula: 2𝑛 = { 𝑛−1
2 + 2𝑛−1 , if 𝑛 > 0.
ALGORITHM A(n)
//Input: a nonnegative integer n
//Output: the value of 2n
if n == 0 return 1
else return A(n-1)+ A(n-1)

The box trace shows that function A(3) returns 8=23.

A(3)

A(2) A(2)

A(1) A(1) A(1) A(1)

A(0) A(0) A(0) A(0) A(0) A(0) A(0) A(0)

A(3)
return 8

A(2) A(2)
return 4 return 4

A(1) A(1) A(1) A(1)

return 2 return 2 return 2 return 2

A(0) A(0) A(0) A(0) A(0) A(0) A(0)

return 1 return 1 return 1 return 1 return 1 return 1 return 1

The algorithm is very inefficient: each time A(n) invokes two recursive calls to A(n-1).
The second recursive call is eliminated in Algorithm B (see next page). Note that the time
complexity of algorithm A(n) is O(2n).

38
 1, if 𝑛 = 0,
(b) The algorithm below uses the recursive formula 2𝑛 = { 𝑛−1
2 × 2 , if 𝑛 > 0.

ALGORITHM B(n) B(3) B(3)

return 2*B(2) return 24=8
//Input: a nonnegative integer n
//Output: the value of 2n
if n == 0 return 1 B(2) B(2)
else return 2*B(n-1) return 2*B(1) return 22=4

The box trace shows that function B(3) returns 8=23.

B(1) B(1)
The time complexity of Algorithm B is O(n): return 2*B(0) return 21=2
- there are n+1 levels in the chain of recursive calls;
- one multiplication is performed in each level, except
for B(0); B(0) B(0)
- thus overall n multiplications are done. return 1 return 1

1, if 𝑛 = 0,
𝑛 2
(c) The next algorithm uses the formula 2𝑛 = (2 ) ,
2 if 𝑛 is even,
𝑛−1 2

{2 × (2 ) , if 𝑛 is odd.
2

ALGORITHM C(n)
//Input: a nonnegative integer n
//Output: the value of 2n
if n == 0 return 1
else
if n%2 == 0
halfPower  C(n/2)
return halfPower * halfPower
else
halfPower  C((n-1)/2)
return 2 * halfPower * halfPower

C(11) C(11) The box trace shows that

halfPower  C(5) halfPower  32 function C(11) returns
return 2*halfPower*halfPower return 23232=2048 2048=2 .11

C(5) C(5) In the recursive version, n

halfPower  C(2) halfPower  4 (or n-1) is halved until the
return 2*halfPower*halfPower return 244=32 result is 0. Thus the number of
recursive calls is bounded by
C(2) C(2) log2n+1.
halfPower  C(1) halfPower  2 Since at most two
return halfPower*halfPower return 22=4 multiplications are done for
each recursive call, the
C(1) C(1) algorithm is O(logn).
halfPower  C(0) halfPower  1
return 2*halfPower*halfPower return 211=2

C(0) 39 C(0)
return 1 return 1
 8.5 The Towers of Hanoi
Another classical example of a recursive algorithm is the recursive solution of the Towers of
Hanoi puzzle. The problem can be described as follows.
Given: - n disks of different size
- three poles: A (the source)
B (the destination)
C (the spare)
- one disk at a time can be moved and it can be placed only on top of a larger disk
Goal: Move all disks from source A to destination B
In order to solve the problem, imagine that function Trs is available to solve the problem of
moving the top n-1 disks from one of the poles to another one. Then a possible solution is
- to use function Trs for moving n-1 disks from the source to the spare pole,
- to move the bottom disk from the source to the destination,
- to use the same function Trs to move the remaining n-1 disks from the spare pole to the
destination.
In the first step and in the third step, function Trs is simply the function to solve the Towers
of Hanoi puzzle but applied to a smaller version of the problem.

ALGORITHM Trs(n, source, destination, spare)

if n = 1
Move a disk directly from source to destination
else
Trs(n-1, source, spare, destination)//Move n-1 disks from source to spare
Trs( 1, source, destination, spare) //Move 1 disk from source to destination
Trs(n-1,spare, destination, source)// Move n-1 disks from spare to destination

Box-tracing for n=3:

40
There are two types of overheads associated with recursive algorithms: processor time
and memory space.
- A recursive call incurs time to create an activation record and to maintain the stack of
activation records. When the call finishes, it takes time to remove the activation record
from the stack and resume execution of the suspended program.
- Additional memory is needed to store a return address (the place in the algorithm from
where the procedure was called) and to store the data used by the procedure.
Complexity Analysis
1) The algorithm’s main operation: moving a disk (or printing a statement about the
move).
Let M(n) denote the number of moves needed to solve the puzzle with n disks.
2) Set up a recurrence relation with initial condition:

the number of moves the number of moves

to relocate n−1 disks to relocate n−1 disks
M(n) = M(n−1) + 1+ M(n−1) for n>1

The number of
moves to relocate one move to relocate
n disks the bottom disk

M(1) = 1 (one move if there is a single disk)

After simplifying the main recurrence relation, we get:
𝑀(𝑛) = 2𝑀(𝑛 − 1) + 1,
𝑀(1) = 1.
3) Solve the recurrence or estimate the rate of growth of its solution
M(n) = 2M(n-1) +1 (substitute M(n-1) = 2M(n-2) + 1)
=2 [2M(n-2) + 1] +1
= 22M(n-2) +2+1 (substitute M(n-2) = 2M(n-3) + 1)
2
=2 [2M(n-3) + 1] + 2 + 1
3
=2 M(n-3) + 22+2+ 1
The above pattern suggests that the next term is
=24M(n-4) + 23+ 22+2+1.
In general, after i substitutions we get:
M(n) = 2iM(n-i) + 2i-1 + 2i-2 + … + 2+1 for 1 ≤ i ≤ n-1.
Substituting i=n-1 we obtain:
M(n) = 2n-1M(n-(n-1)) + 2(n-1)-1+… + 2+1 = 2n-1M(1) + [2n-2+… + 2+1]
= 2n-1M(1) + [2n-1-1]
n-1 n-1 n
=2 + [2 -1] = 2 -1.
Thus we have an algorithm of time complexity O(2n).

If n=64, then M(n)=18,446,744,073,709,551,615.

The program which prints one line for each move would take about 570 years to output the
solution for n=64, if 1,000,000,000 lines are printer per second.

41
 8.6 Fibonacci Numbers
The Fibonacci sequence is a famous series, in which each number is the sum of the previous
two numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
0, if 𝑛 = 0
It is defined recursively as 𝐹(𝑛) = { 1, if 𝑛 = 1
𝐹(𝑛 − 1) + 𝐹(𝑛 − 2), if 𝑛 ≥ 2
Using the above formula, we computing the first few terms:
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5, etc.
Recursive Algorithm
Because the Fibonacci numbers are defined recursively, recursive algorithm is a natural
approach to find the n-th Fibonacci number.
ALGORITHM F(n)
//Computes the n-th Fibonacci number recursively
//Input: a nonnegative integer n
//Output: The nth Fibonacci number
if n  1 return n
else return F(n-1)+F(n-2)

Box-tracing for n=5:

return F(4)+F(3)

F(4)
return F(2)+F(1)
return F(3)+F(2)

F(2) 1F(1)
return F(2)+F(1) return F(1)+F(0) return 1
return F(1)+F(0)

1F(1) 1F(1) 0F(0) 1F(1) 0F(0)

return F(1)+F(0)
return 1 return 1 return 0 return 1 return 0

1F(1) 0F(0)
return 1 return 0 F(5)
return 3+2=5F(5)

F(4) F(3)
return 2+1=3 return 1+1=2F(3)

F(3) F(2) F(2) F(1)

return 1+1=2F(3) return 1+0=1 return 1+0=1F(2) return

F(2) F(1) F(1) F(0) F(1) F(0)

return 1+0=1F(2) return return return return return

F(1) F(0)
return return
42
Although the algorithm is easy to develop, it is extremely inefficient. Each time a recursive
call replaces an instance of size n by two instances of size only slightly smaller than n (the
new instances have sizes n-1 and n-2).
Furthermore, the same value is computed multiple times. As the box-tracing shows, F(2)
is computed three times when calculating F(5).
Complexity Analysis
1) The algorithm’s main operation: addition.
Let A(n) denote the number of additions needed in order to compute the n-th Fibonacci
number.

2) Set up a recurrence relation with initial condition:

the number of additions one addition to add

to calculate F(n-1) F(n-1) and F(n-2)

A(n) = A(n−1) + A(n−2) + 1 for n>1

the number of additions

to calculate the n–th the number of additions
Fibonacci number F(n) to calculate F(n-2)

A(0) = 0 (no additions if n=0)

A(1) = 0 (no additions if n=1)
We have obtained a recurrence relation with two initial conditions:
A(n) = A(n−1) + A(n−2) + 1 for n>1
A(0) = 0
A(1) = 0
3) It can be proved that A(n) is exponential. To be precise, the time complexity is O(n),
1+√5
where  = 2 ≈ 1.61803 is the constant called the golden ratio.
Thus the recursive algorithm for finding the nth Fibonacci number is O(1.62n).

In the iterative algorithm below every Fibonacci number is computed exactly once so that
the time complexity of the algorithm is linear.

Iterative algorithm

ALGORITHM IterativeF(n)
//Computes the n-th Fibonacci number iteratively
//Input: a nonnegative integer n
//Output: The nth Fibonacci number
previous  0 //F(0)
current  1 //F(1)
for i2 to n do
next  current + previous //F(i)
previous  current
current  next
return next 43
Tracing for n=5:
i next previous current In the iterative algorithm IterativeF(n), every
Fibonacci number is computed exactly once. Each
- - 0 1 computation requires one basic operation (addition).
The time complexity of the algorithm is linear, O(n).
2 1 1 1
Clearly, the iterative algorithm for calculating the nth
3 2 1 2 Fibonacci number outperforms the recursive
algorithm. It cannot be recommended to apply
4 3 2 3 recursion in this case. Recursion should be applied
only if a problem has no simple iterative solution.
5 5 3 5

8.7 Merge-Sort
Merge-sort is an efficient sorting algorithm that requires O(nlogn) time to sort an array of n
numbers. Using the ideas of divide-and-conquer, merge-sort splits the array into two
halves. Then it calls recursively itself in order to sort each half. The sorted halves are then
merged together into a sorted array.
For example, if we need to sort 7, 2, 9, 4, 3, 8, 6, 1, then the three steps are performed.
1. Divide the array into two sub-arrays: 7, 2, 9, 4 and 3, 8, 6, 1.
2. Sort each sub-array: 2, 4, 7, 9 and 1, 3, 6, 8.
3. Merge the two sorted sub-arrays: 1, 2, 3, 4, 6, 7, 8, 9.
ALGORITHM mergeSort(A[0..n-1])
//The algorithm sorts a given array by recursive merge-sort
//Input: an array A[0..n-1] of n elements
//Output: array A[0..n-1]sorted in ascending order
if n > 1
copy the first half of A to S1 //divide
copy the second half of A to S2 //divide
mergeSort(S1) //recur
mergeSort(S2) //recur
merge(S1,S2,A) //conquer

Iterative function merge in algorithm mergeSort merges two sorted arrays S1 and S2 by
selecting the smallest element from these arrays and adding it to the beginning of the
output array A. Then the second smallest element is selected from S1 and S2 and added to A.
These steps are continued until one of the two arrays S1 or S2 is empty. Then the remainder
of the other array is copied into the output array A.
ALGORITHM merge(S1[0..p-1], S2[0..q-1], A[0..p+q-1])
//Merges two sorted arrays into one sorted array
//Input: Arrays S1[0..p-1] of p elements and S2[0..q-1] of q
//elements both sorted
//Output: Sorted array A[0..p+q-1] of the elements of S1 and S2
i  0; j  0; k  0
while i < p and j < q do
if S1[i]  S2[j]
A[k]  S1[i]; i  i+1
else A[k]  S2[j]; j  j+1
k  k+1
if i=p
copy S2[j..q-1] to A[k..p+q-1]
44
else copy S1[i..p-1] to A[k..p+q-1]
 Tracing function merge on the two sorted sub-arrays 2, 4, 7, 9 and 1, 3, 6, 8:

k i j S S A (result)
1 2
S1[0] S1[1] S1[2] S1[3] S2[0] S1[1] S2[2] S2[3] A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
0 0 0 2 4 7 9 1 3 6 8 1
1 0 1 2 4 7 9 1 3 6 8 1 2
2 1 1 2 4 7 9 1 3 6 8 1 2 3
3 1 2 2 4 7 9 1 3 6 8 1 2 3 4
4 2 2 2 4 7 9 1 3 6 8 1 2 3 4 6
5 2 3 2 4 7 9 1 3 6 8 1 2 3 4 6 7
6 3 3 2 4 7 9 1 3 6 8 1 2 3 4 6 7 8
7 3 4 2 4 7 9 1 3 6 8 1 2 3 4 6 7 8 9

Box-tracing of the recursive algorithm mergeSort on the array 7, 2, 9, 4, 3, 8, 6, 1 is

illustrated by the following two trees. The root of the left tree represents the initial array
and the splitting point; all other nodes specify sub-arrays after the partitioning. The root of
the right tree represents the output array sorted in ascending order; all other nodes specify
sub-arrays resulting from the merger of two sorted sub-arrays.

Level 3:
Arrays of 7 2 9 43 8 6 1 1 2 3 4 6 7 8 9
length 23=8

Level 2:
Arrays of 7 29 4 3 86 1 2 4 7 9 1 3 6 8
length 22=4

Level 1:
Arrays of 7 9 3 6 2 7 4 9 3 8 1 6
length 21=2 2 4 8 1

Level 0: 7 2 9 4 3 8 6 1 7 2 9 4 3 8 6 1
Arrays of
length 20=1

Complexity Analysis
Method 1. Let us estimate the number of basic operations required to sort an array of n
elements, assuming n is a power of 2. The execution of mergeSort is described by a tree
and we consider operations at each level in the tree.
First we determine the depth of the tree. We number the levels of the tree from the leaves to
the root as Level 0, Level 1, …, Level k, and determine the value of k.

45
At the leaves (Level 0) the arrays are of length 20=1.
In Level 1 the arrays are of length 21=2.
In Level 2 the arrays are of length 22=4.
22 … 2 = 2𝑘 .
In Level k the arrays are of length ⏟
𝑘 times
Now 2k = n, or, equivalently, 𝑘 = log 2 𝑛 .
Now we note that for two sub-arrays S1 and S2 of lengths length(S1) and length(S2)
algorithm merge uses at most
length(S1) + length(S2)-1 = length(A) - 1
key comparisons to merge them into A, since there is at most one comparison each time an
element is put into A. (Note that we count comparisons of keys, the array values)
At any given level in the tree, the combined length of all arrays is always n. So at each level
in the tree, merge uses n or fewer key comparisons.
Hence the total number of key comparisons is bounded by 𝑛𝑘 = 𝑛log 2 𝑛 , and the time
complexity of mergeSort is O(n logn).

Method 2. Assume n=2k.

1) Let C(n) be the worst-case number of key comparisons.
2) Set up a recurrence relation with initial condition:
comparisons incurred by
two call of procedure
mergeSort for
subproblems of size n/2
C(n) = 2C(n/2) + Cmerge(n) = 2C(n/2) + (n-1) for n>1,

the number of key

comparisons to sort comparisons at the
an array of n elements merging stage
(no more than n-1)
C(1) = 0

3) Solving the recurrence:

C(n) = 2C(n/2) + n-1 (substitute C(n/2) = 2C(n/4) + n/2 - 1)
=2 [2C(n/4) + n/2-1] + n-1
= 22C(n/4) + 2n -2-1 (substitute C(n/4) = 2C(n/8) + n/4 - 1)
2
=2 [2C(n/8) + n/4-1]+ 2n -2-1
=23C(n/8) + 3n -22-2-1
The above pattern suggests that the next term is
=24C(n/16) + 4n -23-22-2-1.
In general, after i substitutions we get:
C(n) = 2iC(n/2i) + in -2i-1-2i-2-…-2-1 for 1 ≤ i ≤ k.
The closed form formula is achieved when i=k (recall that n = 2k and k=log2n):
k k-1 k-2 k-1 k-2
C(n) = 2 C(n/2k) + kn -2 -2 -…-2-1 = nC(1) + log2nn – (2 +2 +…+2+1)
= n0 + n log2n –(n-1) = n log2n –(n-1).
Thus the time complexity is O(n logn).

46
 8.8 Quick-Sort
Quick-sort is another recursive sorting algorithm based on the divide-and-conquer
approach.
- Like merge-sort, quick-sort divides the array into two parts and then sorts each part
recursively.
- Unlike merge-sort, the array is partitioned by selecting one element (called the pivot
element) and placing all elements smaller than the pivot before that element and all
larger elements after it. The elements in each of the two parts are not put in order at this
stage. Quick-sort calls recursively itself to sort each part separately.
- The solution is obtained by putting together the first sorted sub-array, the pivot and
then the second sorted sub-array.
There exist various strategies for selecting the pivot element.
We consider the simplest one: pick the first element of the array as its pivot element.
Pivot item

Consider an example of sorting numbers 7, 2, 9, 4, 3, 8, 6, 1.

The first element of the array 7 is selected as the pivot element.
The following steps are performed.
1. Partition the array into two sub-arrays divide

Pivot item

⏟ 4, 3, 6, 1 7 9,
2, ⏟ 8
all smaller all larger

2. Sort each sub-array

Pivot item recur

1, 2, 3, 4, 6 7 ⏟
⏟ 8, 9
sorted sorted

3. Combine the two sorted sub-arrays and the pivot conquer

1, 2, 3, 4, 6, 7, 8, 9.
ALGORITHM quickSort(A[0..n-1])
//The algorithm sorts a given array by recursive quick-sort
//Input: an array A[0..n-1] of n numbers
//Output: the array A sorted in ascending order
if n > 1
pivot  A[0]
copy the elements of A smaller than pivot to S1 //divide
copy the elements of A equal to pivot to S2 //divide
copy the elements of A larger than pivot to S3 //divide
quickSort(S1) //recur
quickSort(S3) //recur
copy the elements back into A in order: //conquer
- first insert the elements of S1,
- then those of S2,
- and finally those of S3.
47
The implementation of quick-sort given above requires extra storage to copy the three parts
of array A to S1, S2 and S3. In fact partition can be done in-place by swapping pairs of
elements (we do not consider this implementation).
Operation of the recursive algorithm quickSort on the array 7, 2, 9, 4, 3, 8, 6, 1 is
illustrated by the following two trees. The nodes of the first tree that specify sub-arrays S1
and S3 are represented by boxes; the nodes of the second tree specify the arrays resulting
from combining two sorted sub-arrays and the pivot.

7 2 9 4 3 8 6 1 2 3 4 6 7 8
1 9

2 4 3 6 1 7 9 1 2 3 4 7 8
8 6 7 9

1 2 4 3 8 9 1 2 3 4 8 9
6 6

3 4 6 3 4 6

Complexity Analysis
The structure of the tree of quick-sort depends essentially on the pivot element. If all
elements of the array are distinct, then in the best case, in each iteration the pivot element
partitions the array into two sub-arrays of equal size. As a result, the number of levels of the
quick-sort tree is no larger than log2n and the total number of comparisons is 𝑛 log 2 𝑛
(similar to merge-sort).
Notice that for the case with repeated elements, the best case instance consists of repeated
copies of the same value. The algorithm performs 𝑛 − 1 comparisons at the partitioning
stage, which results in S1=S3=∅. No further comparisons are done.
In the worst case, after the partition, one sub-array is empty and the other sub-array
contains all remaining elements. Oddly enough, this happens, for example, if the array of n
distinct elements is already sorted in ascending order. Then the algorithm will call itself n
times removing just one element for each call. It creates
- one sub-array of n-1 elements in the first iteration,
- one sub-array of n-2 elements in the second iteration,
- one sub-array of n-3 elements in the next iteration,
- …
- one sub-array of 1 element in the last iteration.
Method 1. The total number of key comparisons performed for partitioning is equal to the
sum of the lengths of the sub-arrays in all iterations:
(n-1) + (n-2) + … + 2 + 1 = ½ n(n-1),
i.e., the time complexity of quick-sort is O(n2). Observe that O(n2) is the time complexity of
quick-sort in the worst case.
Quick-sort algorithm is important because of its average-case behaviour. It can be shown
that the average number of key comparisons made by quick-sort on a randomly generated
array is proportional to nlog2n. In practice, quick sort is usually faster than merge-sort.
Besides, in-place implementation of quick-sort does not require additional memory.

48
In-class exercise:
Consider operation of quick-sort on the array
(1, 2, 3, 4, 5, 6, 7)
The task is to sort the array in ascending order. Draw the tree of recursive calls.

Method 2.
1) Let C(n) be the worst-case number of key comparisons of quickSort. The worst case
happens if after each partition sub-array S1 is empty and sub-array S3 contains all
remaining elements.
2) Set up a recurrence relation with initial condition:
comparisons incurred comparisons incurred
by quicksort(S1) by quicksort(S3)

C(n) = C(0) + C(n-1) + n-1 for n>1,

the number of key

comparisons to sort n-1 comparisons to partition A into S1, S2, S3
an array of n elements

C(1) = C(0) = 0
𝐶(𝑛 − 1) + (𝑛 − 1), if 𝑛 ≥ 2
Thus 𝐶(𝑛) = {
0, if 𝑛 ≤ 1
3) Solving the recurrence:
C(n) = C(n-1) + (n-1) (substitute C(n-1) = C(n-2) + (n-2))
= [C(n-2) + (n-2)] + (n-1)
= C(n-2) + (n-2) + (n-1) (substitute C(n-2) = C(n-3) + (n-3))
=[C(n-3) + (n-3)] + (n-2) + (n-1)
= C(n-3) + (n-3) + (n-2) + (n-1)
The above pattern suggests that the next term is
= C(n-4) + (n-4) + (n-3) + (n-2) + (n-1).
In general, after i substitutions we get:
C(n) = C(n-i) + (n-i) + (n-i+1) + … + (n-2) + (n-1) for 1 ≤ i ≤ n-1.
The closed form formula is achieved when i=n-1:
C(n) = C(1) + (1+2+…+(n-2)+(n-1)) = 0 + ½ n(n-1).
Thus the time complexity is O(n2).

49
 Conclusions
We have considered five sorting algorithms: selection sort, insertion sort, bubble sort,
merge-sort and quick-sort.
Selection sort is an iterative algorithm based on a so-called brute force approach. It is an
easy straightforward method. Two other popular iterative sorting algorithms are insertion
sort and bubble sort. The time complexity of all three iterative algorithms (selection sort,
insertion sort and bubble sort) is O(n2).

Merge-sort and quick-sort are based on the divide-and-conquer approach. The running time
of quick-sort is O(n2) in the worst case. Merge-sort algorithm represents a substantial
improvement over quadratic-time algorithms as its time complexity is O(nlog2n).
It can be shown that if we limit ourselves to algorithms that sort by making comparisons,
then no better algorithms are possible, i.e., no algorithm can make less than nlog2n
comparisons in the worst case.
The results on the worst-case performance of the sorting algorithms are summarised in the
following table.
Approach Sorting algorithms Sorting algorithm with
with time complexity time complexity
O(n2) O(nlog2n)
Brute Force Selection Sort
Bubble Sort
Insertion Sort
Divide-and-Conquer Quick-Sort Merge-Sort
This table does not compare the average-case performance of algorithms. Theoretical and
empirical analysis shows that quick-sort is usually preferred to merge-sort. In practice
quick-sort is probably used more often than any other sorting algorithm.
Observe that for small number of elements n quadratic-time algorithms may outperform
merge-sort and quick-sort.
The efficiency of sorting algorithms can be compared empirically. The table below is taken
from A. Drozdek “Data Structures and Algorithms in C++”, Brooks/Cole, 2001. The
experiment was run on a Pentium 133 MHz PC. The table indicates that when the input size
doubles, the running time of quadratic algorithms grows approximately by a factor of 4,
while the running times of merge-sort and quick-sort grows approximately by a factor of 2.

n
10,000 20,000 40,000 80,000
Selection Sort 5.17 sec. 22.03 sec. 1 min. 31.01 sec. 6 min. 6.30 sec.
Insertion Sort 3.18 sec. 13.51 sec. 53.66 sec 3 min. 46.62 sec.
Bubble Sort 10.88 sec. 45.09 sec. 2 min. 59.40 sec. 12 min. 27.15 sec.
Merge-Sort 0.05 sec. 0.11 sec 0.22 sec. 0.49 sec.
Quick-Sort 0.05 sec. 0.05 sec 0.11 sec. 0.28 sec.

50
In-class exercise:

The recursive algorithms for the following problems are based on solving two sub-problems
of smaller size:
- the Towers of Hanoi;
- the recursive algorithm to find the nth Fibonacci number;
- binary search;
- calculating 2n as 2n-1+ 2n-1;
- calculating 2n as (2n/2)2 if n is even, or 2(2n/2)2, if n is odd;
- Merge Sort.

For each recursive algorithm, specify the sizes of the sub-problems and classify the
algorithm as efficient or inefficient.

Efficient recursive algorithms: Inefficient recursive algorithms:

Problem The sizes of the Problem The sizes of the

sub-problems sub-problems

A divide-and-conquer algorithm can be more efficient than a straightforward brute-force

solution if a problem of size n is reduced to a problem of size n/2, or if it is divided into two
problems of size n/2.

51
 8.9 Recursive and Iterative Solutions to the k-Combinations Problem

A selection of k elements from a set of n elements is called a k-combination. In a k-

combination, the order of the elements does not matter and repetition is not allowed. The
number of k-combinations of a set of n elements is denoted by C(n,k).
For example, if n=4, then selecting k=2 objects can be done in C(4,2)=6 ways. For the set X =
{a,b,c,d} of 4 elements, the 2-combinations are {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}.
The number of k-combinations can be found recursively:

1, if k = 0 or n = k
C (n, k ) = 
C (n − 1, k − 1) + C (n − 1, k ), if n  k  0
The recursive formula is obtained by fixing one particular object (say, object a) from the list
and representing C(n,k) as the sum of

the number of k-combinations and the number of k-combinations

that include object a, that do not include object a
C(n-1, k-1) C(n-1, k)

The algorithm that implements this formula is presented below.

ALGORITHM C(n, k)
//Calculates the number of k-combinations of a set of n objects
//Input: nonnegative integers n and k, n  k//Output: the number
of k-combinations
if k == 0 or n == k return 1
else return C(n-1,k-1)+C(n-1,k)

Box-tracing (please complete)

C(4,2) C(4,2)
return C(3,1)+C(3,2) return …+ …

C(3,1) C(3,2) C(3,1) C(3,2)

return C(2,0)+C(2,1) return C(2,1)+C(2,2) return …+ … return…+ …

C(2,0) C(2,1) C(2,1) C(2,2) C(2,0) C(2,1) C(2,1) C(2,2)

return 1 return C(1,0)+C(1,1) returnC(1,0)+C(1,1) return 1 return 1 return …+ … return …+ … return 1

C(1,0) C(1,1) C(1,0) C(1,1) C(1,0) C(1,1) C(1,0) C(1,1)

return 1 return 1 return 1 return 1 return 1 return 1 return 1 return 1

C(4,2) returns …

52
The recursive algorithm is inefficient: each time a recursive call replaces an instance of size
n by two instances of size n-1 (almost of size n).

The iterative algorithm presented below implements the same formula

1, if k = 0 or n = k
C (n, k ) = 
C (n − 1, k − 1) + C (n − 1, k ), if n  k  0

ALGORITHM Combinations1(n, k)
//Calculates the number of k-combinations of a set of n objects
//Input: nonnegative integers n and k, n  k//Output: the
number of k-combinations
for i0 to n
for j0 to min{i,k}
if j==0 or i==j
C[i,j]  1
else C[i,j]  C[i-1,j-1] + C[i-1,j]
return C(n,k)

Trace the algorithm for n=5, k=2 and determine its running time.

53
Another formula for calculating the number of k-combinations is

n!
C (n, k ) =
k!(n − k )!
One possible iterative algorithm that implements this formula is presented below.

ALGORITHM Combinations2(n,k)
//Input: nonnegative integers n and k, nk.
//Output: the value of C(n,k)
f k == 0 or n == k return 1
else
//Calculating n!
product1  1
for i1 to n do
product1  product1 * i

//Calculating k!
product2  1
for i1 to k do
product2  product2 * i

//Calculating (n-k)!
product3  1
for i1 to n-k do
product3  product3 * i

//Calculating C(n,k)
return product1/(product2*product3)

What is the time complexity of this algorithm?

Exercise. Simplify the formula above and develop a more efficient iterative algorithm.

54
 Recursion – Pros and Cons

Pros
• For some problems it can be easier to develop a recursive algorithm.
- The recursive algorithm for the Towers of Hanoi is an example of a simple
algorithm for a difficult problem.
- There are a number of algorithms that are inherently recursive: Euclid’s algorithm
for finding the highest common factor, binary search and merge sort.

• A recursive solution may be simpler than an equivalent iterative algorithm.

- The recursive algorithm for the Fibonacci sequence is more simple than its iterative
counterpart

• Recursive algorithms are useful for backtracking when it is necessary to enumerate

different outcomes of decisions (traversing a maze, various search problems).

Cons
• If a recursive algorithm and an iterative one have the same running time in terms of
big-O, the recursive algorithm might be slower in practice: computer has to do
additional “bookkeeping” for suspended calls.
- The running time of the recursive and iterative algorithms for calculating n! is the
same, O(n), but the actual computation time of the recursive program may be larger
than the actual computation time of the iterative program due overheads of
recursive calls.

• A recursive algorithm can be extremely inefficient if it computes the same value over
and over.
- The recursive algorithm for the Fibonacci sequence is an example of a poor solution
to an easy problem. Its running time is exponential. An iterative algorithm is much
faster as it has linear running time.
- Computing 2n recursively as 2n-1+2n-1 requires exponential time while computing 2n
as 22n-1 requires linear time.
- Computing the number of k-combinations recursively also incurs repeated
calculations of the same values.

55