Design and Analysis of Algorithms

Getting started
Reference:
CLRS Chapter 2

Topics:
• the basic concepts
• asymptotic analysis

Huo Hongwei 1
 Algorithms

• Algorithm.
– A well-defined computational procedure that takes
some value,or set of values, as input and produces
some value,or set of values, as output.

Input Algorithm Output

– issues: correctness, efficiency(amount of work done

and space used), storage(simplicity,clarity), optimality
.etc.

Huo Hongwei 2
 The problem of sorting

• Input: sequence <a1, a2,…,an> of n natural numbers

• Output: permutation <a’1, a’2,…,a’n> such that

a’1≤ a’2 ≤ … ≤ a’n

• Example
– Input: <5, 2, 4, 6, 1, 3>
– Output: <1, 2, 3, 4, 5, 6>

Huo Hongwei 3
 Insertion Sort
INSERTION SORT
INSERTION-SORT(A)
1 for j ← 2 to length(A)
2 do key ← A[j]
3 // insert A[j] into the sorted sequence A[1..j-1]
4 i ← j – 1
5 while i > 0 and A[i] > key
6 do A[i+1] ← A[i] // move item back
7 i ← i – 1
8 A[i+1] ← key //find the insertion position

1 i j n
A:
key
sorted
Huo Hongwei 4
 Insertion Sort Example

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
(a) 5 2 4 6 1 3 (b) 2 5 4 6 1 3 (c) 2 4 5 6 1 3

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
(d) 2 4 5 6 1 3 (e) 1 2 4 5 6 3 (f) 1 2 4 5 6 3

• The operation of INSERTION-SORT on the array A = < 5, 2, 4,

6, 1, 3 >.

Huo Hongwei 5
 Analysis of Insertion sort
INSERTION SORT

INSERTION-SORT(A) cost times

1 for j ← 2 to length(A) c1 n
2 do key ← A[j] c2 n-1
3 // insert A[j] into the sorted
sequence A[1..j-1] 0 n-1
4 i ← j – 1 c4 n-1
n
5 while i > 0 and A[i] > key c5 ∑ j=2 tj
n
6 do A[i+1] ← A[i] c6 ∑ j=2(tj –1)
i ← i – 1 n
7 c7
∑ j=2(tj –1)
8 A[i+1] ← key c8 n-1

tj : the number of times the while loop test in line 5 is executed for
that value of j
Huo Hongwei 6
 Analysis of Insertion sort

• To compute T(n), the running time of Insertion-sort, we

sum the products of the cost and times columns,
obtaining

T(n)=c1n + c2(n-1) + c4(n-1) + c5 ∑ n tj + c6 ∑ n (tj –1)

j=2 j=2
n
+c7 ∑ (tj –1) + c8(n-1)
j=2

• The best-case occurs if the array is already sorted.

T(n)=c1n + c2(n-1) + c4(n-1) + c5 (n-1) + c8(n-1)
= ( c1 + c2+ c4 + c5 + c8) n- (c2+ c4 + c5 + c8)
– The running time is a linear function of n

Huo Hongwei 7
 Analysis of Insertion sort

• The worst-case results if the array is in reverse sorted

order – that is, in decreasing order.
T(n)= c1n + c2(n-1) + c4(n-1) + c5 (n(n+1)/2-1) + c6(n(n-1)/2)
+ c7 (n(n-1)/2) + c8(n-1)
= (c5/2 + c6/2 + c7/2)n2
+ ( c1 + c2 + c4+ c5/2 – c6/2 – c7/2 + c8 ) n – (c2 + c4 + c5+ c8)
– The running time is a quadratic function of n
n n
∑ j=2 tj = ∑ j=2 j = n(n+1)/2 -1

n n
∑ j=2 tj -1 = ∑ j=2 ( j–1) = n(n-1)/2

Huo Hongwei 8
 Worst-case and Average-case Analysis

• Note:
– Upper bound on the running time for any input
– For some algorithms, worst-case occur fairly often.
» e.g. Searching in a database for a particular piece
of information
– Average case often as bad as worst case (but not
always!)

Huo Hongwei 9
 Order of Growth

• We will only consider order of growth of running time:

– We can ignore the lower-order terms, since they are
relatively insignificant for very large n.
– We can also ignore leading term’s constant
coefficients, since they are not as important for the
rate of growth in computational efficiency for very
large n.
– We just said that best case was linear in n and
worst/average case quadratic in n.

Huo Hongwei 10
 Designing Algorithms

• We discussed insertion sort

– We introduced RAM model of computation
– We analyzed insertion sort in the RAM model
– We discussed how we are normally only interested in
growth of running time:
» Best-case linear in O(n), worst-case quadratic in
O(n2)
• Can we design better than n2 sorting algorithm?
• We will do so using one of the most powerful algorithm
design techniques.

Huo Hongwei 11
 Divide-and-Conquer

• Recursive in structure

• To solve P:
– Divide P into smaller problems P1, P2, …, Pk.
– Conquer by solving the (smaller) subproblems
recursively.
– Combine the solutions to P1, P2, …, Pk into the solution
for P.

Huo Hongwei 12
 Merge Sort Algorithm

• Using divide-and-conquer, we can obtain a merge-sort

algorithm
– Divide: Divide the n elements into two subsequences
of n/2 elements each.
– Conquer: Sort the two subsequences recursively.
– Combine: Merge the two sorted subsequences to
produce the sorted answer.

• Assume we have procedure MERGE(A, p, q, r) which

merges sorted A[p...q] with sorted A[q+1..r] in (r - p) time.

Huo Hongwei 13
 Merge-Sort (A, p, r)

INPUT: a sequence of n numbers stored in array A

OUTPUT: an ordered sequence of n numbers
MERGESORT
MERGE-SORT(A,p,r)
1 if p < r
2 then q ← ⎣(p+r)/2⎦
3 MERGE-SORT (A, p, q)
4 MERGE-SORT (A, q+1, r)
5 MERGE (A, p, q, r)

Huo Hongwei 14
 Merge
MERGE
MERGE(A, p, q, r)
1 n1 ← q-p+1;
2 n2 ← r-q;
3 create arrays L[1..n1+1] and R[1..n2+1]
4 for i ← 1 to n1
5 do L[i] ← A[p + i-1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1+1] ← ∞
9 R[n2+1] ← ∞ //set sentinel
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i] < R[j]
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1
Huo Hongwei 15
 Action of Merge Sort

1 2 2 3 4 5 6 7
merge

2 4 5 7 1 2 3 6
merge merge

2 5 4 7 1 3 2 6

merge merge merge merge

5 2 4 7 1 3 2 6
initial sequence

Huo Hongwei 16
 Analysis divide-and-conquer algorithms

• Let T(n) be the running time on a problem of size n.

– Suppose that our division of the problem yields a
subproblems, each of which is 1/b the size of the
original.
– D(n) the time to divide the problem into subproblems
– C(n) the time to combine the solutions to subproblems
into the solution to the original problem

Θ(1) if n < c
T(n ) =
aT(n/b) + D(n) + C(n) otherwise

Recurrence Equation

Huo Hongwei 17
 Mergesort Analysis
• How long does mergesort take?
– Bottleneck = merging (and copying).
» merging two files of size n/2 requires n comparisons
– T(n) = comparisons to mergesort n elements.
» to make analysis cleaner, assume n is a power of 2

Θ(1) if n = 1,
T(n ) =
2T( n/2) + Θ(n) otherwise
Sorting both halves merging

• Claim. T(n) = n lg2 n.

– Note: same number of comparisons for ANY file.
» even already sorted
– We'll prove several different ways to illustrate standard
techniques.

Huo Hongwei 18
 Proof by Picture of Recursion Tree
Θ(1) if n = 1,
T(n ) =
2T( n/2) + cn otherwise
Sorting both halves merging

T(n)

Huo Hongwei 19
 Proof by Picture of Recursion Tree
Θ(1) if n = 1,
T(n ) =
2T( n/2) + cn otherwise
Sorting both halves merging

c(n)

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

Huo Hongwei 20
 Proof by Picture of Recursion Tree
Θ(1) if n = 1,
T(n ) =
2T( n/2) + cn otherwise
Sorting both halves merging

cn

cn/2 cn/2

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

Huo Hongwei 21
 Construction of recursion tree
cn n

cn/2 cn/2 2(n /2)

cn/4 cn/4 cn/4 cn/4 4(n /4)

lgn
...
n / 2k 2k (n / 2k)
...
c c c c c c c c cn

Total: cn lgn + cn

The fully expanded tree has lg n +1 levels, i.e., it has height lg n, and
each level contributes a total cost of cn. The total cost is Θ(n lg n).

Huo Hongwei 22