Kinds of analyses Worst-case:(usually) T(n)=maximum time of algorithm on any input of size n Average-case:(sometimes) T(n)=expected time of algorithm over all inputs of size n Need assumption of statistical distribution of inputs Best-case:(bogus) Cheat with a slow algorithm that works fast on some inputKinds of analyses Worst-case: (usually) T( n) = maximum time of algorithm on any input of size n. Average-case: (sometimes) T( n) = expected time of algorithm over all inputs of size n. Need assumption of statistical distribution of inputs. Best-case: (bogus) Cheat with a slow algorithm that works fast on some input