L3 - Characterizing Running Time.pdf

CP312 Algorithm Design and Analysis I LECTURE 3: CHARACTERIZING RUNNING TIME 1 Simplifying the Running Time Expression Consider the following running time: 𝑇 𝑛 = 𝑎0 + 𝑎1 𝑛 + 𝑎2 𝑛2 + 𝑎3 𝑛3 + ⋯ + 𝑎𝑑 𝑛𝑑 ◦ ◦ ◦ ◦ Too complicated Too many terms Difficult to compare two expressions of the same form Do we r...

CP312 Algorithm Design and Analysis I LECTURE 3: CHARACTERIZING RUNNING TIME 1 Simplifying the Running Time Expression Consider the following running time: 𝑇 𝑛 = 𝑎0 + 𝑎1 𝑛 + 𝑎2 𝑛2 + 𝑎3 𝑛3 + ⋯ + 𝑎𝑑 𝑛𝑑 ◦ ◦ ◦ ◦ Too complicated Too many terms Difficult to compare two expressions of the same form Do we really need that many terms? Example: 𝑇 𝑛 = 10𝑛3 + 𝑛2 + 40𝑛 + 800 ◦ If 𝑛 = 1000, then 𝑇 𝑛 = 10,001,040,800 whereas 10𝑛3 = 10,000,000,000 ◦ If we approximate and drop all but the 𝑛3 term the error is 0.01% ◦ So, it is worth simplifying a complexity expression to get the core factor in that expression 2 Simplifying the Running Time Expression ◦ Only the dominant terms of a polynomial matter in the long run ◦ Lower-order terms fade to insignificance as the problem input size increases ◦ We care more about scalable algorithms than those for specific small-size inputs 3 Growth Rate of Running Time For any given running time function, in order to write it in the best way that represents the general growth rate. 1. We consider only the most dominant term ◦ Keep the fastest growing term and remove the lower-order terms 2. Constant coefficients are removed ◦ ◦ These constants represent language- or machine-dependent overhead Growth rate not affected by constant coefficients Examples: ◦ ◦ 𝑇 𝑛 = 100𝑛 + 105 is considered a linear function 𝑇 𝑛 = 80𝑛2 + 50𝑛 + 10 is considered a quadratic function 4 Asymptotic Complexity For large enough 𝑛: 𝑇 𝑛 ≈ 𝑔(𝑛) Finding the exact complexity, 𝑇 𝑛 = number of primitive operations, of an algorithm is difficult. Therefore, we approximate 𝑇(𝑛) by a function 𝑔(𝑛) in a way that does not substantially change the magnitude of 𝑇(𝑛) ◦ The function 𝑔(𝑛) is sufficiently close to 𝑇(𝑛) for sufficiently large values of the input size 𝒏. This "approximate" measure of efficiency is called asymptotic complexity. Thus, the asymptotic complexity measure does not give the exact number of operations of an algorithm, but it shows how that number grows with the size of the input. ◦ This gives us a measure that will work for different operating systems, compilers and CPUs. 5 Asymptotic Complexity Three main types of asymptotic complexity expressions: 1. Big-𝑶 ◦ Express asymptotic upper bounds 2. Big-𝛀 ◦ Express asymptotic lower bounds 3. Big-𝚯 ◦ Express asymptotic tight bounds 𝑇 𝑛 =𝑂 𝑔 𝑛 ⇒ For large enough 𝑛, 𝑇 𝑛 ≤ 𝑐𝑔 𝑛 𝑇 𝑛 =Ω 𝑔 𝑛 ⇒ For large enough 𝑛, 𝑇 𝑛 ≥ 𝑐𝑔 𝑛 𝑇 𝑛 =Θ 𝑔 𝑛 ⇒ For large enough 𝑛, 𝑐1 𝑔 𝑛 ≤ 𝑇 𝑛 ≤ 𝑐2 𝑔 𝑛 The term asymptotically means “for large enough 𝑛” 6 Asymptotic Notation Recall: Informally, we said that 𝑓 𝑛 = Θ 𝑔 𝑛 if 𝑓 𝑛 = 𝑔(𝑛) after removing lower order terms and constant factors. Definition: For a given function 𝑔 𝑛 , we denote by Θ 𝑔 𝑛 set of functions: Θ 𝑔 𝑛 the ∃𝑐1 , 𝑐2 , 𝑛0 > 0 such that ∀𝑛 ≥ 𝑛0 = 𝑓 𝑛 ቤ 0 ≤ 𝑐1 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐2 𝑔 𝑛 7 Asymptotic Notation Θ 8 Asymptotic Notation Θ Example: 1 2 𝑛 2 − 3𝑛 = Θ(𝑛2 ) 𝑐1 Pick 𝑐1 = 1 ,𝑐 14 2 = 𝑛2 1 2 ≤ 𝑛 − 3𝑛 ≤ 𝑐2 𝑛2 2 1 3 𝑐1 ≤ − ≤ 𝑐2 2 𝑛 1 , 𝑛0 2 =7 9 Asymptotic Notation Θ Example: Is 4𝑛4 = Θ(𝑛2 )? NO Proof by Contradiction: Assume there exists 𝑐2 and 𝑛0 such that 4𝑛4 ≤ 𝑐2 𝑛2 for all 𝑛 ≥ 𝑛0 Then 𝑛2 ≤ 𝑐2 /4 for all 𝑛 ≥ 𝑛0 Which is NOT TRUE since 𝑐2 is a constant → Contradiction 10 Asymptotic Notation 𝑂 Definition: For a given function 𝑔 𝑛 , we denote by 𝑂 𝑔 𝑛 set of functions: 𝑂 𝑔 𝑛 the ∃𝑐, 𝑛0 > 0 such that ∀𝑛 ≥ 𝑛0 = 𝑓 𝑛 ቤ 𝑓 𝑛 ≤ 𝑐𝑔 𝑛 11 Asymptotic Notation 𝑂 We use 𝑂-notation to give an upper bound on a function. 𝑓 𝑛 =Θ 𝑔 𝑛 ⟹𝑓 𝑛 =𝑂 𝑔 𝑛 Suppose 𝑇𝑤 (𝑛) is the worst-case running-time of an algorithm (on input 𝑤) and 𝑇𝑦 (𝑛) is the running-time of an algorithm on any input 𝑦. Then 𝑇𝑤 𝑛 = 𝑂 𝑔 𝑛 ⟹ 𝑇𝑦 𝑛 = 𝑂 𝑔 𝑛 12 Asymptotic Notation 𝑂 13 Asymptotic Notation 𝑂 Examples: Is 2𝑛+1 = 𝑂 2𝑛 ? YES 14 Asymptotic Notation 𝑂 Examples: Is 22𝑛 = 𝑂 2𝑛 ? NO 15 Asymptotic Notation 𝑂 Examples: Is 22𝑛 = 2𝑂(𝑛) ? YES 16 Asymptotic Notation 𝑂 Examples: Is log10 (𝑛) = 𝑂 log 2 𝑛 ? YES 17 Asymptotic Notation 𝑂 Examples: Is 𝑛2.5 = 𝑂 𝑛2.8 ? YES 18 Asymptotic Notation 𝑂 Examples: Is 𝑛log 𝑛 = 𝑂 𝑛5 ? NO 19 Asymptotic Notation Ω Definition: For a given function 𝑔 𝑛 , we denote by Ω 𝑔 𝑛 set of functions: Ω 𝑔 𝑛 the ∃𝑐, 𝑛0 > 0 such that ∀𝑛 ≥ 𝑛0 = 𝑓 𝑛 ቤ 0 ≤ 𝑐𝑔 𝑛 ≤ 𝑓 𝑛 20 Asymptotic Notation Ω We use Ω-notation to give an lower bound on a function. 𝑓 𝑛 =Θ 𝑔 𝑛 ⟹𝑓 𝑛 =Ω 𝑔 𝑛 Suppose 𝑇𝑏 (𝑛) is the best-case running-time of an algorithm (on input 𝑏) and 𝑇𝑦 (𝑛) is the running-time of an algorithm on any input 𝑦. Then 𝑇𝑏 𝑛 = Ω 𝑔 𝑛 ⟹ 𝑇𝑦 𝑛 = Ω 𝑔 𝑛 21 Asymptotic Notation Ω 22 The Useful Bounds 23 Asymptotic Notation 𝑜 and 𝜔 𝑜 𝑔 𝑛 ∀𝒄 = 𝑓 𝑛 ቮ∃𝑛0 > 0 such that ∀𝑛 ≥ 𝑛0 𝑓 𝑛 < 𝑐𝑔 𝑛 𝑓 𝑛 lim =0 𝑛→∞ 𝑔 𝑛 𝜔 𝑔 𝑛 ∀𝒄 = 𝑓 𝑛 ቮ∃𝑛0 > 0 such that ∀𝑛 ≥ 𝑛0 𝑐𝑔 𝑛 < 𝑓 𝑛 𝑓 𝑛 lim =∞ 𝑛→∞ 𝑔 𝑛 24 Asymptotic Notation 𝑜 and 𝜔 Examples: Is 10𝑛 = 𝑜 𝑛 ? NO Is 2𝑛2 = 𝜔 𝑛 ? YES 25 Asymptotic Notation Properties Transitivity for Θ, 𝑂, Ω, o, 𝜔 ◦ E.g. If 𝑓 𝑛 = Θ 𝑔 𝑛 and 𝑔 𝑛 = Θ ℎ 𝑛 then 𝑓 𝑛 = Θ ℎ 𝑛 Reflexivity for Θ, 𝑂, Ω ◦ E.g. 𝑓 𝑛 = Θ 𝑓 𝑛 Symmetry for Θ ◦ 𝑓 𝑛 =Θ 𝑔 𝑛 if and only if 𝑔 𝑛 = Θ 𝑓 𝑛 Transpose Symmetry for 𝑂, Ω, o, 𝜔 ◦ 𝑓 𝑛 =𝑂 𝑔 𝑛 if and only if 𝑔 𝑛 = Ω 𝑓 𝑛 ◦ 𝑓 𝑛 =𝑜 𝑔 𝑛 if and only if 𝑔 𝑛 = 𝜔 𝑓 𝑛 26 Asymptotic Notation Properties Using asymptotic notation in equations: 8𝑛2 + 7n + 10 = 8n2 + 𝑂 𝑛 ◦ ⟹ 8𝑛2 + 7𝑛 + 10 = 8𝑛2 + 𝑓(𝑛) for some 𝑓 𝑛 = 𝑂(𝑛) 8𝑛2 + 𝑂 𝑛 = 𝑂(𝑛2 ) ◦ ⟹ For any 𝑔 𝑛 = 𝑂(𝑛), 8𝑛2 + 𝑔(𝑛) = 𝑓(𝑛) for some 𝑓 𝑛 = 𝑂(𝑛2 ) 27 Exercises EX: Given that 𝑓 𝑛 = 𝑂 𝑛3 + 𝑂 𝑛2 lg 𝑛 , simplify 𝑓 𝑛 so that only a single big-O is used. 30 Exercises EX: List the following functions from slowest to fastest (𝑐 is an arbitrary constant): ◦ ◦ ◦ ◦ ◦ ◦ ◦ 𝑂 log 𝑛 𝑂 𝑛2 𝑂(𝑐 𝑛 ) 𝑂(1) 𝑂 log 𝑛 𝑂(𝑛𝑐 ) 𝑂 𝑛 Notation Name 𝑂(1) Constant 𝑂(log 𝑛) 𝑂 log 𝑛 𝑐 𝑂 1 ⊆ 𝑂 log 𝑛 ⊆ 𝑂 𝑛 ⊆ 𝑂 𝑛 log 𝑛 ⊆ 𝑂 𝑛2 ⊆ 𝑂 𝑛3 ⊆ 𝑂 2𝑛 𝑐 Logarithmic Polylogarithmic 𝑂(𝑛) Linear 𝑂(𝑛2 ) Quadratic 𝑂(𝑛𝑐 ) Polynomial 𝑂(𝑐 𝑛 ) Exponential 32