How Fast is It? Time (and Space)Complexity of Algorithms 02 o W Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05.20206/43
How Fast is It? Time (and Space) Complexity of Algorithms O Ω Θ o ω Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 6 / 43
Space Complexity of Algorithms We only care about the extra space caused by the algorithm. The space for inputs is not part of space complexity of algorithms. INSERTION-SORT(A,n):O(1)(constant) Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,20207/43
Space Complexity of Algorithms We only care about the extra space caused by the algorithm. The space for inputs is not part of space complexity of algorithms. insertion-sort(A, n) : O(1) (constant) Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 7 / 43
Is it the Fastest? 2I63 Complexity of Problems This is much harder and is not our focus today. Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms March05,20208/43
Is it the Fastest? Complexity of Problems This is much harder and is not our focus today. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 8 / 43
PROBLEM Whenever you design an algorithm, you provide an upper bound for the complexity of the problem. Whenever you encounter a "hardcore"of the problem, you obtain a lower bound for all possible algorithms. Often,there is an"algorithmic gap"between them. When the gap is gone,you get the optimal algorithm. sorting(A,n):θ(n log n)=O(n log n)∩2(n log n) Hengfeng Wei (bfweiinju.edu.cn)2-2 The Efficiency of Algorithms March05,20209/43
Whenever you design an algorithm, you provide an upper bound for the complexity of the problem. Whenever you encounter a “hardcore” of the problem, you obtain a lower bound for all possible algorithms. Often, there is an “algorithmic gap” between them. When the gap is gone, you get the optimal algorithm. sorting(A, n) : Θ(n log n) = O(n log n) ∩ Ω(n log n) Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 9 / 43
Q:How fast is your algorithm? A:It runs 3.1415926 seconds. TLE TIME LIMIT EXCEEDEEEED. TRICRS TO AVOID TLE IN COMPETITVE CODING B6OcKS Hengfeng Wei (hfweiinju.edu.cn2-2 The Efficiency of Algorithms March05,202010/43
Q : How fast is your algorithm? A : It runs 3.1415926 seconds. Hengfeng Wei (hfwei@nju.edu.cn) 2-2 The Efficiency of Algorithms March 05, 2020 10 / 43