ESc101 : Fundamental of Computing
I Semester 2008-09
Lecture 38
• Analyzing the number of steps in Quick Sort.
• Why the exact values of constants in an + c are ignored
• Time Complexity of algorithms.
• Examples ...
1
Number of instructions taken in Quick Sort
2
Quick Sort uses the method Partition
int Partition(int[] A, int left, right)
3
What does Partition(int[] A, int left, right) do ?
For an element x∈ {A[left],...,A[right]}, do rearrangement so that
Left Right
A
... x ...
<x >x
We used x=A[right]
Number of instructions = c(right - left)
4
What does Partition(int[] A, int left, right) do ?
For an element x∈ {A[left],...,A[right]}, do rearrangement so that
Left Right
A
... x ...
<x >x
We used x=A[right]
Number of instructions = c(right - left)
5
What does Partition(int[] A, int left, right) do ?
For an element x∈ {A[left],...,A[right]}, do rearrangement so that
Left Right
A
... x ...
<x >x
We used x=A[right]
Number of instructions = c(right - left), for some constant c
6
public static void Qsort(int[] A, int left, int right)
{
if(left<right)
{
int mid = partition(A, left, right);
Qsort(A,left,mid-1);
Qsort(A,mid+1,right);
}
}
mid is the position of pivot element after partition()
What values can mid take ?
7
Number of instructions taken in Quick Sort on n numbers
For array A = {1, 9, 5, 21, 40, 29, 13}
8
Quick sort on {1, 9, 5, 21, 40, 29, 13}
QSort(A,0,6)
Level 2
QSort(A,4,6)
QSort(A,0,2)
Level 1
QSort(A,0,0) QSort(A,2,2) QSort(A,4,4) QSort(A,6,6)
Level 0
9
Number of instructions taken in Quick Sort on n numbers
For array A = {40, 29, 21, 13, 9, 5, 1}
10
Quick sort on {40, 29, 21, 13, 9, 5, 1}
QSort(A,0,6)
Level 6
QSort(A,1,6)
QSort(A,0,−1) Level 5
QSort(A,1,0) QSort(A,2,6)
Level 4
QSort(A,2,1) QSort(A,3,6)
Level 3
QSort(A,3,2) QSort(A,4,6)
Level 2
QSort(A,5,6)
QSort(A,4,3) Level 1
QSort(A,5,4) QSort(A,6,6)
Level 0
11
Number of instructions taken in Quick Sort on n numbers
• If in each recursive call, the pivot element partitions the array into equal half
always, then the number of instructions is =
????
• If in each recursive call, the pivot element is always either the smallest or
greatest, then the number of instructions is =
cn(n − 1).
12
Number of instructions taken in Quick Sort on n numbers
• If in each recursive call, the pivot element partitions the array into equal half
always, then the number of instructions is =
cn log n
• If in each recursive call, the pivot element is always either the smallest or
greatest, then the number of instructions is =
cn(n − 1).
13
Number of instructions taken in Quick Sort on n numbers
• If in each recursive call, the pivot element partitions the array into equal half
always, then the number of instructions is =
cn log n.
• If in each recursive call, the pivot element is always either the smallest or
greatest, then the number of instructions is =
?????.
14
Number of instructions taken in Quick Sort on n numbers
• If in each recursive call, the pivot element partitions the array into equal half
always, then the number of instructions is =
cn log n.
• If in each recursive call, the pivot element is always either the smallest or
greatest, then the number of instructions is =
dn2 , for some constant d.
15
Why is Quick Sort still the most efficient practically ?
1. No overhead of extra array and copying like in Merge sort.
2. The fraction of premutations which correspond to the worst case is very very
small.
3. As a consequence, the average number of steps are close to the best case :
O(n log n).
For a formal analysis, do the course
ES0211 : Data structures and Algorithms
16
Why is Quick Sort still the most efficient practically ?
1. No overhead of extra array and copying like in Merge sort.
2. The fraction of premutations which correspond to the worst case is very very
small.
3. As a consequence, the average number of steps are close to the best case :
O(n log n).
For a formal analysis, do the course
ES0211 : Data structures and Algorithms
17
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : 10n + 200
• Algorithm B worst case number of instructions : 10n + 100000
Answer : Algorithm A
18
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : 10n + 200
• Algorithm B worst case number of instructions : 10n + 100000
Answer : Algorithm A
19
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : n2 + 10n +1000
• Algorithm B worst case number of instructions : n2 + n
Answer : Algorithm B
20
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : n2 + 10n +1000
• Algorithm B worst case number of instructions : n2 + n
Answer : Algorithm B
21
Interesting question on the following slide ...
22
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : 10n + 200
• Algorithm B worst case number of instructions : n2
Answer : ????
For n < 20, B is faster and for n > 20, A is faster
23
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : 10n + 200
• Algorithm B worst case number of instructions : n2
Answer : ????
For n < 20, B is faster and for n > 20, A is faster
24
Realize the following important fact
The number of instructions executed or the time taken by an algorithm becomes
an important issue only when the input is very large.
So we should compare the number of instructions of two algorithms for
asymptotically large values of input.
25
Which of the two algorithms would you call faster than the other?
• Algorithm A worst case number of instructions : 10n + 200
• Algorithm B worst case number of instructions : n2
Answer :
Asmptotically A is faster than B
26
Time complexity of an algorithm
Definition :
it is a measure of how many steps are executed by an algorithm on a given input
asymptotically, i.e., for large input size.
27
Worst case time complexity of an algorithm
Definition : Over all inputs of size n, what is the worst case number of steps
taken by the algorithm ?
28
