Scribd
Upload
71 views74 pages

Lecture1 Asymptotic Anal

The document discusses the CS514 course on design and analysis of algorithms. It covers asymptotic performance and how algorithms behave as problem size increases. It then provides an example of insertion sort, walking through the steps on a sample input array to sort it. The example shows how insertion sort iterates through the array, finds the correct insertion point for each element, and inserts it to build up the sorted array.

Uploaded by

Vikas Rai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
71 views74 pages

Lecture1 Asymptotic Anal

The document discusses the CS514 course on design and analysis of algorithms. It covers asymptotic performance and how algorithms behave as problem size increases. It then provides an example of insertion sort, walking through the steps on a sample input array to sort it. The example shows how insertion sort iterates through the array, finds the correct insertion point for each element, and inserts it to build up the sorted array.

Uploaded by

Vikas Rai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 74

CS514: Design and Analysis

of Algorithms

Asymptotic Performance
Correctness
Reference
About

Visit:
 http://172.16.1.3/~abyaym/

Contact Me:
 abyaym@iitp.ac.in

Meeting Time:
 Anytime based on availability
Asymptotic Performance

• Asymptotic performance: How does algorithm


behave as the problem size gets very large?
o Running time
o Memory/storage requirements
 Remember that we use the RAM model:
o All memory equally expensive to access
o No concurrent operations
o All reasonable instructions take unit time
 Except, of course, function calls
o Constant word size
 Unless we are explicitly manipulating bits
An Example: Insertion Sort
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 10 40 20 j =  i =  key = 
A[i] =  A[i+1] = 
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 10 40 20 j=2 i=1 key = 10
A[i] = 30 A[i+1] = 10
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 j=2 i=1 key = 10
A[i] = 30 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 j=2 i=1 key = 10
A[i] = 30 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 j=2 i=0 key = 10
A[i] =  A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
30 30 40 20 j=2 i=0 key = 10
A[i] =  A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=2 i=0 key = 10
A[i] =  A[i+1] = 10
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=0 key = 10
A[i] =  A[i+1] = 10
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=0 key = 40
A[i] =  A[i+1] = 10
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=0 key = 40
A[i] =  A[i+1] = 10
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=2 key = 40
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=2 key = 40
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=3 i=2 key = 40
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=4 i=2 key = 40
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=4 i=3 key = 20
A[i] = 40 A[i+1] = 20
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 20 j=4 i=3 key = 20
A[i] = 40 A[i+1] = 20
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 j=4 i=3 key = 20
A[i] = 40 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 j=4 i=3 key = 20
A[i] = 40 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 j=4 i=3 key = 20
A[i] = 40 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 40 40 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 40
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 j=4 i=2 key = 20
A[i] = 30 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 j=4 i=1 key = 20
A[i] = 10 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 30 30 40 j=4 i=1 key = 20
A[i] = 10 A[i+1] = 30
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 20 30 40 j=4 i=1 key = 20
A[i] = 10 A[i+1] = 20
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
An Example: Insertion Sort
10 20 30 40 j=4 i=1 key = 20
A[i] = 10 A[i+1] = 20
1 2 3 4
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
} Done!
An Example: Insertion Sort

• How to prove the correctness???


Insertion Sort: Correctness

• Loop invariant: At the start of each iteration of


the for loop, the subarray A[1…j-1] consists of
the elements originally in A[1…j-1], but in
sorted order.
InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
Insertion Sort: Correctness
• Three things about the loop invariant:

InsertionSort(A, n) {
for j = 2 to n {
key = A[j]
i = j - 1;
while (i > 0) and (A[i] > key) {
A[i+1] = A[i]
i = i - 1
}
A[i+1] = key
}
}
Analysis: Running Time
Analysis: Running Time
Analysis: Running Time

• Best Case

• Average Case??
Analysis: Running Time

• Simplifications
 Ignore actual and abstract statement costs
 Order of growth is the interesting measure:
o Highest-order term is what counts
 Remember, we are doing asymptotic analysis
 As the input size grows larger it is the high order term that
dominates
Asymptotic Notation
(Upper Bound)

• We say InsertionSort’s run time is O(n2)


 Properly we should say run time is in O(n2)
 Read O as “Big-O” (you’ll also hear it as “order”)
Insertion Sort is O(n2)

• Proof
 Suppose runtime is an2 + bn + c
o If any of a, b, and c are less than 0 replace the constant
with its absolute value
 an2 + bn + c  (a + b + c)n2 + (a + b + c)n + (a + b + c)
 3(a + b + c)n2 for n  1
 Let c’ = 3(a + b + c) and let n0 = 1
• Question
 Is InsertionSort O(n3)?
 Is InsertionSort O(n)?
Big O Fact

• A polynomial of degree k is O(nk)


• Proof:
 Suppose f(n) = bknk + bk-1nk-1 + … + b1n + b0
o Let ai = | bi |
 f(n)  aknk + ak-1nk-1 + … + a1n + a0
i
n
 n  ai k
k
 n k
a i  cn k

n
o- and - Asymptotic Notations

• Intuitively,

 o() is like <  () is like >


 O() is like   () is like 

 () is like =
Practical Complexity

250

f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Practical Complexity

500

f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Practical Complexity

1000

f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n

0
1 3 5 7 9 11 13 15 17 19
Practical Complexity

5000

4000
f(n) = n
f(n) = log(n)
3000
f(n) = n log(n)
f(n) = n^2
2000 f(n) = n^3
f(n) = 2^n

1000

0
1 3 5 7 9 11 13 15 17 19
Proof By Induction

• Claim:S(n) is true for all n >= k


• Basis:
 Show formula is true when n = k
• Inductive hypothesis:
 Assume formula is true for an arbitrary n
• Step:
 Show that formula is then true for n+1
Induction Example:
Gaussian Closed Form
• Prove 1 + 2 + 3 + … + n = n(n+1) / 2
 Basis:
o If n = 0, then 0 = 0(0+1) / 2
 Inductive hypothesis:
o Assume 1 + 2 + 3 + … + n = n(n+1) / 2
 Step (show true for n+1):
1 + 2 + … + n + n+1 = (1 + 2 + …+ n) + (n+1)
= n(n+1)/2 + n+1 = [n(n+1) + 2(n+1)]/2
= (n+1)(n+2)/2 = (n+1)(n+1 + 1) / 2
Induction Example:
Geometric Closed Form
• Prove a0 + a1 + … + an = (an+1 - 1)/(a - 1) for
all a  1
 Basis: show that a0 = (a0+1 - 1)/(a - 1)
a0 = 1 = (a1 - 1)/(a - 1)
 Inductive hypothesis:
o Assume a0 + a1 + … + an = (an+1 - 1)/(a - 1)
 Step (show true for n+1):
a0 + a1 + … + an+1 = a0 + a1 + … + an + an+1
= (an+1 - 1)/(a - 1) + an+1 = (an+1+1 - 1)/(a - 1)
Induction
• We’ve been using weak induction
• Strong induction also holds
 Basis: show S(0)
 Hypothesis: assume S(k) holds for arbitrary k <= n
 Step: Show S(n+1) follows
• Another variation:
 Basis: show S(0), S(1)
 Hypothesis: assume S(n) and S(n+1) are true
 Step: show S(n+2) follows

You might also like