Slide 1
CST 5320
Design/Analysis of Algorithms
Lecture 1: Asymptotic Complexity (1)
Instructor: Debzani De
*
Things that are Important
Syllabus is available in Canvas. Read it carefully.
Reading Material
Asymptotic Complexity
Cormen Chapter 2 and 3.
Insertion sort
Chapter 4:Page 131 to 136.
https:
opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/InsertionSort.html
Review: Asymptotic Performance
Asymptotic performance: How does algorithm behave as the problem size gets very large?
Running time
Memory/storage requirements
Remember that we use the RAM model:
All memory equally expensive to access
No concu
ent operations
All reasonable instructions take unit time
Except, of course, function calls
Constant word size
Unless we are explicitly manipulating bits
Review: Running Time
Number of primitive steps that are executed
Except for time of executing a function call most statements roughly require the same amount of time
Worst case vs. average case vs. best case
*
Measuring Input Sizes
Algorithm efficiency/complexity is defined as a function of input size.
Input size depends on the problem.
Sorting – The number of items to be sorted.
Graphs – The number of vertices and/or edges
Numerical – the number of bits needed to represent a numbe
*
*
Units for Measuring Running Time
Measure the running time using standard unit of time measurements, such as seconds, minutes?
Depends on computer speed, # of programs running, etc.
count the number of times each of an algorithm’s operations is executed.
Difficult and unnecessary
count the number of times an algorithm’s basic operation is executed.
Basic operation: the most important operation of the algorithm, the operation contributing the most to the total running time.
For example, the basic operation is usually the most time-consuming operation in the algorithm’s innermost loop.
*
Basic Operations
Example Basic Operations
one arithmetic operation (e.g., +, *).
one assignment
one comparison (e.g., x >= 0)
one read
one write
When we consider the complexity of an algorithm, we don't really care about the exact number of basic operations that are performed; instead, we care about how the number of basic operations relates to the problem input size. If the input size doubles, does the number of basic operations stay the same? double? increase in some other way?
*
*
Input Size and Basic Operation Examples
Problem Input size measure Basic operation
Search for a key in a list of n items Number of items in list, n comparison
Sort a list of n elements Number of items in the list, n comparison
Add two n by n matrices Matrix dimension or total number of elements Addition
Find the first element of a list Number of items in list, n read
Initialize all items of a list with value 99. Number of items in list, n assignment
*
*
Worst case Efficiency
Efficiency (# of times the basic operation will be executed) for the worst case input of size n.
The algorithm runs the longest among all possible inputs of size n.
Best case Efficiency
Efficiency (# of times the basic operation will be executed) for the best case input of size n.
The algorithm runs the fastest among all possible inputs of size n.
Average case Efficiency:
Efficiency (#of times the basic operation will be executed) for a typical
andom input of size n.
Worst-Case, Best-Case, and Average-Case Efficiency
*
Algorithmic complexity/efficiency
To find the efficiency of an algorithm, follow the below steps
What is the input size?
What is its basic operation?
How many times is the basic operation executed?
Is there any best, worst or average case for this algorithm, or all cases are equal?
What is the efficiency class of this algorithm?
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
10
40
20
0
1
2
3
i =  j =  key = 
A[j] =  A[j+1] = 
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
10
40
20
0
1
2
3
i = 1 j = 0 key = 10
A[j] = 30 A[j+1] = 10
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
30
40
20
0
1
2
3
i = 1 j = 0 key = 10
A[j] = 30 A[j+1] = 30
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
30
40
20
0
1
2
3
i = 1 j = 0 key = 10
A[j] = 30 A[j+1] = 30
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
30
40
20
0
1
2
3
i = 1 j = -1 key = 10
A[j] =  A[j+1] = 30
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
30
30
40
20
0
1
2
3
i = 1 j = -1 key = 10
A[j] =  A[j+1] = 30
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
0
1
2
3
i = 1 j = -1 key = 10
A[j] =  A[j+1] = 10
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
0
1
2
3
i = 2 j = -1 key = 10
A[j] =  A[j+1] = 10
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
0
1
2
3
i = 2 j = -1 key = 40
A[j] =  A[j+1] = 10
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
0
1
2
3
i = 2 j = -1 key = 40
A[j] =  A[j+1] = 10
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 2 j = 1 key = 40
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 2 j = 1 key = 40
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 2 j = 1 key = 40
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 2 j = 1 key = 40
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 3 j = 1 key = 20
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 3 j = 1 key = 20
A[j] = 30 A[j+1] = 40
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
20
1
2
3
4
i = 3 j = 2 key = 20
A[j] = 40 A[j+1] = 20
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
}
10
30
40
20
1
2
3
4
i = 3 j = 2 key = 20
A[j] = 40 A[j+1] = 20
0
1
2
3
An Example: Insertion Sort
InsertionSort(A, n) {
for i = 1 to n {
key = A[i]
j = i - 1;
while (j >= 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
}
}
10
30
40
40
1
2
3
4
i = 3 j = 2 key = 20