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-5Copyright © 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