Best-case, average-case, worst-case For some algorithms, efficiency depends on form of input: o Worst case: Worst(n)- maximum over inputs of size n o Best case: Cbest()- minimum over inputs of size n D Average case: Cavg(n)-"average over inputs of size n Number of times the basic operation will be executed on typical input NOT the average of worst and best case Expected number of basic operations considered as a random variable under some assumption about the probability distribution of all possible inputs. So, avg=expected under uniform distribution. Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-5
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-5 Best-case, average-case, worst-case For some algorithms, efficiency depends on form of input: Worst case: Cworst(n) – maximum over inputs of size n Best case: Cbest(n) – minimum over inputs of size n Average case: Cavg(n) – “average” over inputs of size n • Number of times the basic operation will be executed on typical input • NOT the average of worst and best case • Expected number of basic operations considered as a random variable under some assumption about the probability distribution of all possible inputs. So, avg = expected under uniform distribution
Example: Sequential search ALGORITHM SequentialSearch(A[0.n-1, K) //Searches for a given value in a given array by sequential search //Input: An array A[O n-1 and a search key K //Output: The index of the first element of A that matches K or-1 if there are no matching elements ←0 while i< n and a[i]≠kdo ←-i+1 if i<n return i else return-1 口 Worst case n key comparisons 口 Best case comparisons D Average case (n+1)/2, assuming K is in A Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-6
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-6 Example: Sequential search Worst case Best case Average case n key comparisons 1 comparisons (n+1)/2, assuming K is in A
Types of formulas for basic operation's count 口 Exact formula nn n Formula indicating order of growth with specific multiplicative constant eg,C(m)≈0.5m o Formula indicating order of growth with unknown multiplicative constant C(m)≈cn2 Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-7
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-7 Types of formulas for basic operation’s count Exact formula e.g., C(n) = n(n-1)/2 Formula indicating order of growth with specific multiplicative constant e.g., C(n) ≈ 0.5 n 2 Formula indicating order of growth with unknown multiplicative constant e.g., C(n) ≈ cn2
Order of growth o Most important: Order of growth within a constant multiple as n->00 D Example: How much faster will algorithm run on computer that is twice as fast? How much longer does it take to solve problem of double input size? Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2 2-8
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-8 Order of growth Most important: Order of growth within a constant multiple as n→∞ Example: • How much faster will algorithm run on computer that is twice as fast? • How much longer does it take to solve problem of double input size?
Values of some important functions as n->00 og 272 3.31013.3101021 3.6.10 1026.61026.6-1021041061.310309.31015 10 01031.0.104106109 04131041.31056108102 171051.71061010 1015 106201062010710121018 Table 2.1 Values(some appraximate)of several functions important for analysis of algorithms Copyright 2007 Pearson Addison-Wesley. All rights reserved A Levitin "Intoducion to the Design Analysis of Algorithms, 2nd ed, Ch 2
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 2 2-9 Values of some important functions as n →