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/43Whenever 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