(^22) | Chapter 2: The Mathematics of Algorithms
Iftmeasures the work done by an algorithm on each instance, then the average-
case work done by an algorithm onSn is:
That is, the actual work done on instancesi,t(si), is weighted with the probability
thatsiwill actually be presented as input. If Pr{si}=0, then the actual value oft(si)
does not impact the expected work done by the program. Denoting this average-
case work onSnbyTac(n), then the rate of growth ofTac(n) defines the average-
case complexity of the algorithm.
Recall that when describing the rate of growth of work or time, we consistently
ignore constants. So when we say that SEQUENTIALSEARCHofnelements takes,
on average:
probes (subject to our earlier assumptions), then by convention we simply say
that subject to these assumptions, we expect SEQUENTIALSEARCHwill examine a
linear number of elements, ororder n.
Best-Case
Knowing the best case for an algorithm is useful even though the situation rarely
occurs in practice. In many cases, it provides insight into the optimal circum-
stance for an algorithm. For example, the best case for SEQUENTIALSEARCHis
when it searches for a desired value,v, which ends up being the first element in
the list. A slightly different approach, which we’ll call COUNTINGSEARCH,
searches for a desired value,v, and counts the number of times thatvappears in
the list. If the computed count is zero, then the item was not found, so it returns
false; otherwise, it returnstrue. Note that COUNTINGSEARCHalways searches
through the entire list; therefore, even though its worst-case behavior is O(n)—the
same as SEQUENTIALSEARCH—its best-case behavior remains O(n), so it is
unable to take advantage of either the best-case or average-case situations in
which it could have performed better.
Performance Families
We compare algorithms by evaluating their performance on input data of sizen.
This methodology is the standard means developed over the past half-century for
comparing algorithms. By doing so, we can determine which algorithms scale to
solve problems of a nontrivial size by evaluating the running time needed by the
algorithm in relation to the size of the provided input. A secondary form of perfor-
mance evaluation is to consider how much memory or storage an algorithm
needs; we address these concerns within the individual algorithm chapters, as
appropriate.
Tac()n
1
Sn-------- ts()iPr{}si
si∈Sn= ∑
1
2
---n^1
2+---
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use