How Fast is It? 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
How Fast is It? Time (and Space)Complexity of Algorithms 4口￥0,43，t夏里Q0 Hengfeng Wei (hfweiinju.edu.cn)2-2 The Efficiency of Algorithms farch05.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
How Fast is It? Time (and Space)Complexity of Algorithms 02 o W 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweiinju.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 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
Space Complexity of Algorithms We only care about the extra space caused by the algorithm. 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