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. 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
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) 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
Is it the Fastest? 2I63 Complexity of Problems 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
Is it the Fastest? 2I63 Complexity of Problems This is much harder and is not our focus today. 4口，1①，43，t夏，30Q0 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