Designing algorithms

 There are many ways to design an algorithm.

 Insertion sort uses an incremental approach: having

sorted the sub-array A[1…j - 1], we insert the single
element A[ j] into its proper place, yielding the sorted
sub-array A[1…j].

 Another approach to design is the divide-and-conquer

approach which has a recursive structure to solve a
given problem;
 they break the problem into several sub-problems that are
similar to the original problem but smaller in size,
 solve the sub-problems recursively,
 and then combine these solutions to create a solution to the
original problem.
1
The divide-and-conquer
approach
 Recursive in structure

 Divide the problem into several smaller sub-

problems that are similar to the original but
smaller in size
 Conquer the sub-problems by solving them
recursively. If they are small enough, just solve
them in a straightforward manner.
 Combine the solutions to create a solution to the
original problem

2
An Example: Merge Sort
 Divide: Divide the n-element sequence to be
sorted into two subsequences of n/2
elements each
 Conquer: Sort the two subsequences
recursively using merge sort.
 Combine: Merge the two sorted
subsequences to produce the sorted answer.

3
Merge Sort
 To sort n numbers
 if n = 1 done!
 recursively sort 2 lists of
numbers n/2 and n/2
elements
 merge 2 sorted lists in O(n)
time
 Strategy
 break problem into similar
(smaller) subproblems
 recursively solve subproblems
 combine solutions to answer

4
 .Merge Sort cont

[8, 3, 13, 6, 2, 14, 5, 9, 10, 1, 7, 12, 4]

[8, 3, 13, 6, 2, 14, 5] [9, 10, 1, 7, 12, 4]

[8, 3, 13, 6] [2, 14, 5] [9, 10, [7, 12, 4]

1]
[8, [13, 6] [2, 14] [5] [9, 10] [1] [7, 12] [4]
3]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
5
 .Merge Sort cont

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13,14]

[2, 3, 5, 6, 8, 13, 14] [1, 4, 7, 9, 10,12]

[3, 6, 8, 13] [2, 5, 14] [1, 9, [4, 7, 12]

10]
[3, [6, 13] [2, 14] [5] [9, 10] [1] [7, 12] [4]
8]
[8] [3] [13] [6] [2] [14] [9] [10] [7] [12]
6
Merge Sort Procedure
 The procedure MERGE-SORT(A, p, r) sorts the elements
in the sub-array A[ p…r].
 The divide step simply computes an index q that partitions
A[ p…r] into two sub-arrays: A[ p…q], containing n/2
elements, and A[ q + 1…r], containing n/2 elements.
 To sort the entire sequence
A ={A[1], A[2], . . . ,
A[ n]}, we make the initial
call MERGE-SORT( A, 1,
length[ A]), where
length[ A] = n.

7
8
Merge algorithm

9
Merge Sort
 The key operation of the merge sort algorithm is the
merging of two sorted sequences in the "combine" step.
To perform the merging, we use an auxiliary procedure
MERGE(A, p, q, r), where A is an array and p, q, and r
are indices numbering elements of the array such that p ≤
q < r.

 The procedure assumes that the sub-arrays A[ p…q] and

A[ q + 1…r] are in sorted order. It merges them to form a
single sorted sub-array that replaces the current sub-array
A[ p…r].

10
 .Merge algorithm cont

 The operation of lines 10-17 in the call MERGE(A, 9, 12, 16).

11
.Merge algorithm cont
 The operation of lines 10-17 in the call MERGE(A, 9, 12, 16)

12
Analysis of Merge Sort
Statement Effort
MergeSort(A, left, right) { T(n)
if (left < right) { (1)
mid = floor((left + right) / 2); (1)
MergeSort(A, left, mid); T(n/2)
MergeSort(A, mid+1, right); T(n/2)
Merge(A, left, mid, right); (n)
}
}

 So T(n) = (1) when n = 1, and

2T(n/2) + (n) when n > 1

13
Analysis of Merge Sort
 Divide: computing the middle takes O(1)
 Conquer: solving 2 sub-problem takes 2T(n/2)
 Combine: merging n-element takes O(n)
 Total:
T(n) = O(1) if n = 1
T(n) = 2T(n/2) + O(n) + O(1) if n > 1
 T(n) = O(n lg n)
 Solving this recurrence (how?) gives T(n) = O(n lg n)
 This expression is a recurrence
 To simplify the analysis we assume that the original
problem size is a power of 2. Each divide step then yields
two subsequences of size exactly n/2.
14
 .Analysis of Merge Sort cont
Assume n=2k for k>=1
T(n) = 2 T(n/2) + bn + c
T(n/2) = 2T((n/2) /2) + b(n/2) + c
= 2[2T(n/4) + b(n/2) + c] + bn +c
= 4 T(n/4)+ bn +2c +bn +c
=4 T(n/4) + 2bn+ (1 + 2) c = 22 T(n/22)+2bn+(20+21)
= 4 [2T((n/4)/2) + b(n/4) + c] +2bn + (1+2)c
=8 T(n/8) + 3bn+ (1+2+4)c
=23 T(n/23) + 3bn+ (20+21+22)c

How many steps k=x

=2k T(n/2k) +kbn+(20+21+…+2k-1)c are needed to
T(1) = a, since n=2k 
log n = log2k = k eliminate the
T(n) = 2k. a + k bn + (20+21+…+2k-1) c , but recurence ?
= b. n log n + (a + c) n – c
= O (n log n) Worst case

15
The Recursion Tree Method
 The recursion tree method for solving
recurrences:
 converts the recurrence into a tree of the recursive
function calls.
 Each node has a cost, representing the workload of
the corresponding call (without the recursive calls
done there). The total workload results by adding the
workloads of all nodes. It uses techniques for
bounding summations.
 Example: applying the recursion tree method for
solving the MergeSort recurrence
Recursion tree: T(n)=2
*T(n/2)+n
T(n) n n

T(n/2) T(n/2) n/2 n/2

T(n/4) T(n/4)T(n/4) T(n/4)

The recursion tree has to be expanded until it reaches its leafs.

To compute the total runtime we have to sum up the costs of all the
nodes:
• Find out how many levels there are

• Find out the workload on each level

 Recursion tree: T(n)=2
*T(n/2)+n n n

n/2 n/2
n
log 2 n
n/4 n/4 n/4 n/4
n

T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)

n

Θ(n * log2 n)
 Analysis Of Recursive Binary
int binarySearch (int target, int[] array,
Search
if (low > high)
int low, int high) {

return -1;
else {
int middle = (low + high)/2;
if (array[middle] == target)
return middle;
else if(array[middle] < target)
return binarySearch(target, array, middle + 1, high);
else
return binarySearch(target, array, low, middle - 1);
}
}
 The recurrence relation for the running time of the method is:
T(1) = a if n = 1 (one element array)
T(n) = T(n / 2) + b if n > 1
Analysis Of Recursive Binary
Search (Cont’d)
Without loss of generality, assume n, the problem size, is a multiple of 2, i.e., n = 2 k

Expanding:
T(1) = a (1)
T(n) = T(n / 2) + b (2)
= [T(n / 22) + b] + b = T (n / 22) + 2b by substituting T(n/2) in
(2)
= [T(n / 23) + b] + 2b = T(n / 23) + 3b by substituting T(n/22)
in (2)
= ……..
= T( n / 2k) + kb

The base case is reached when n / 2k = 1  n = 2k  k = log2 n, we then

have:

T(n) = T(1) + b log2 n

= a + b log2 n
Forming Recurrence Relations
(Cont’d)
Write the recurrence relation for the following method:

public int g(int n) {

if (n == 1)
return 2;
else
return 3 * g(n / 2) + g( n / 2) + 5;
}
The base case is reached when n == 1. The method performs one comparison
and one return statement. Therefore, T(1), is some constant c.

When n > 1, the method performs TWO recursive calls, each with the parameter n
/ 2, and some constant # of basic operations.

Hence, the recurrence relation is:

T(1) = c for some constant c
T(n) = b + 2T(n / 2) for some constant b
Forming Recurrence Relations
(Cont’d)
Write the recurrence relation for the following method:

long fibonacci (int n) { // Recursively calculates Fibonacci number

if( n == 1 || n == 2)
return 1;
else
return fibonacci(n – 1) + fibonacci(n – 2);
}

The base case is reached when n == 1 or n == 2. The method performs one

comparison and one return statement. Therefore each of T(1) and T(2) is some
constant c.

When n > 2, the method performs TWO recursive calls, one with the parameter n -
1 , another with parameter n – 2, and some constant # of basic operations.

Hence, the recurrence relation is:

T(n) = c if n = 1 or n = 2
T(n) = T(n – 1) + T(n – 2) + b if n > 2
Forming Recurrence Relations
(Cont’d)
Write the recurrence relation for the following method:
long power (long x, long n) {
if(n == 0)
return 1;
else if(n == 1)
return x;
else if ((n % 2) == 0)
return power (x, n/2) * power (x, n/2);
else
return x * power (x, n/2) * power (x, n/2);
}
The base case is reached when n == 0 or n == 1. The method performs one comparison and
one return statement. Therefore T(0) and T(1) is some constant c.

At every step the problem size reduces to half the size. When the power is an odd number,
an additional multiplication is involved. To work out time complexity, let us consider the worst
case, that is we assume that at every step an additional multiplication is needed. Thus total
number of operations T(n) will reduce to number of operations for n/2, that is T(n/2) with
seven additional basic operations (the odd power case)

Hence, the recurrence relation is:

T(n) = c if n = 0 or n = 1
T(n) = 2T(n /2) + b if n > 2
Solving Recurrence Relations
To solve a recurrence relation T(n) we need to derive a form of
T(n) that is not a recurrence relation. Such a form is called a
closed form of the recurrence relation.

There are five methods to solve recurrence relations that

represent the running time of recursive methods:
 Iteration method (unrolling and summing)

 Substitution method (Guess the solution and verify by induction)

 Recursion tree method

 Master theorem (Master method)

 Using Generating functions or Characteristic equations

Inthis course, we will use the Iteration method and a

simplified Master theorem.
Solving Recurrence Relations -
Iteration
Steps: method
 Expand the recurrence
 Express the expansion as a summation by plugging the recurrence back into
itself until you see a pattern.
 Evaluate the summation
 In evaluating the summation one or more of the following summation
formulae may be used:
 Arithmetic series:

• Special Cases of Geometric Series:

 Geometric Series:
Solving Recurrence Relations - Iteration method
(Cont’d)
 Harmonic Series:

 Others:
 Analysis Of Recursive

Factorial method
Example1: Form and solve the recurrence relation for the
running time of factorial method and hence determine its big-
O complexity: long factorial (int n) {
if (n == 0)
return 1;
else
return n * factorial (n – 1);
}
T(0) = c (1)
T(n) = b + T(n - 1) (2)
= b + b + T(n - 2) by subtituting T(n – 1) in (2)
= b +b +b + T(n - 3) by substituting T(n – 2) in (2)
…
= kb + T(n - k)
The base case is reached when n – k = 0  k = n, we then have:
T(n) = nb + T(n - n)
= bn + T(0)
= bn + c
Therefore the method factorial is O(n)