Lecture 2
Preliminaries How
to estimate time complexity? preliminaries -- master theorem
Mathematical
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Review“Computer Science is the study of algorithms.” -- Donald E. Knuth
Problems
Algorithms
Complexity
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Review“Computer Science is the study of algorithms.” -- Donald E. Knuth
ProblemsInput Output
Algorithms
Complexity
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Review“Computer Science is the study of algorithms.” -- Donald E. Knuth
ProblemsInput Output
AlgorithmsSolve the problem Terminate
Complexity
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Review“Computer Science is the study of algorithms.” -- Donald E. Knuth
ProblemsInput Output
AlgorithmsSolve the problem Terminate
ComplexityFunction of the input size
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Roadmap How to estimate time complexity?
counting basic operations worst case, average case, amortized analysis
Mathematical preliminaries
Logarithm, oor and ceiling function, pigeonhole principle Recurrence relations -- master theoremXiaojuan Cai, School of Software, SJTU. All rights reserved.
Counting the Iterations
Iterations
Algorithm 1.7 Count1 Input: n= 2k, for some positive integer k. Output: count= number of times Step 4 is executed. 1. 2. 3. 4. 5. 6. 7. 8. count← 0; while n≥ 1 for j← 1 to n count← count+ 1 end for n← n/2 end while return count
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Counting the Iterations
Iterations
Algorithm 1.7 Count1 Input: n= 2k, for some positive integer k. Output: count= number of times Step 4 is executed. 1. count← 0; 2. while n≥ 1 3. for j← 1 to n 4. count← count+ 1 5. end for 6. n← n/2 7. end while n n n n n+8. return count j+···+ log n= 2n 1=θ(n)+ 2+···+ 2 2 2 2Xiaojuan Cai, School of Software, SJTU. All rights reserved.
Iterations Counting the IterationsAlgorithm 1.8 Count2 Input: A positive integer n. Output: count= number of times Step 5 is executed. 1. 2. 3. 4. 5. 6. 7. 8. count← 0; for i← 1 to n m← n/i for j← 1 to m count← count+ 1 end for end for return countXiaojuan Cai, School of Software, SJTU. All rights reserved.
The inner for is executed n, n/2 , n/4 , . . ., n/n times
Iterations Counting the IterationsAlgorithm 1.8 Count2 Input: A positive integer n. Output: count= number of times Step 5 is executed. 1. 2. 3. 4. 5. 6. 7. 8. count← 0; for i← 1 to n m← n/i for j← 1 to m count← count+ 1 end for n n n n n n end for ( 1)≤ ≤ i i i return count i=1 i=1 i=1Xiaojuan Cai, School of Software, SJTU. All rights reserved.
The inner for is executed n, n/2 , n/4 , . . ., n/n times
Countin
g the Iterations
Iterations
Algorithm 1.9 Count3 2k, k is a positive integer. Input: n= 2 Output: count= number of times Step 6 is executed. 1. 2. 3. 4. 5. 6. 7. 8. 9. count← 0; for i← 1 to n j← 2; while j≤ n j← j 2; count← count+ 1 end while end for return countXiaojuan Cai, School of Software, SJTU. All rights reserved.
Counting the Iterations
Iterations
Algorithm 1.9 Count3 2k, k is a positive integer. Input: n= 2 Output: count= number of times Step 6 is executed. 1. 2. 3. 4. 5. 6. 7. 8. 9. count← 0; for i← 1 to n j← 2; while j≤ n j← j 2; count← count+ 1 end while end for return count
O(nloglogn)All rights reserved.
Xiaojuan Cai, School of Software, SJTU.
Recurrenceint fib_rec (int n){ ! if (n==1|| n==2){ ! ! return! 1; !} ! else{ ! ! return fib_rec(n-1)+ fib_rec(n-2); !}}T (n) T (n) S(n)=>= T (n 1)+ T (n 2)+ 2, T (1), T (2)< 3 Fibn T (n)Xiaojuan Cai, School of Software, SJTU. All rights reserved.
“Sandwich rule”2, 13, 43, 45, 89 6, 24, 51, 90, 93
2, 6, 13, 24, 43, 45, 51, 89, 90, 93
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
“Sandwich rule”2, 13, 43, 45, 89 6, 24, 51, 90, 93
2, 6, 13, 24, 43, 45, 51, 89, 90, 93
Minimal: n Maximal: 2n-1
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
“Sandwich rule”2, 13, 43, 45, 89 6, 24, 51, 90, 93
2, 6, 13, 24, 43, 45, 51, 89, 90, 93
Minimal: n Maximal: 2n-1
Θ(n)Xiaojuan Cai, School of Software, SJTU. All rights reserved.
Analysis method Worst case analysis Average case analysis Amortized analysisXiaojuan Cai, School of Software, SJTU. All rights reserved.
Worst case analysis
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Worst case analysisLinearSearch isΘ(n) in worst case.
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Worst case analysisLinearSearch isΘ(n) in worst case. BinarySearch isΘ(logn) in worst case.
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.
Worst Case Analysis
Worst case analysisLinearSearch isΘ(n) in worst case. BinarySearch isΘ(logn) in worst case. Consider the following algorithm:
1. if n is odd then k← BinarySearch(A, x) 2. else k← LinearSearch(A, x)
In the worst case, the running time is (log(n)) and O(n
Xiaojuan Cai, School of Software, SJTU.
All rights reserved.