Why this matters
Two runs of the same program can take very different amounts of work. A search for the name "Ada" in a list of 1,000 names might stop at the first name, or it might read all 1,000 names and then say "not found". The code is identical. The input is different.
When you describe how fast an algorithm is, you need to say which input you mean. Engineers use three names for three situations. The best case is the input that makes the work smallest. The worst case is the input that makes the work largest. The average case is the work you expect over the inputs you might see.
This lesson applies those three names to three common tools: linear search, quicksort and hash lookup. You will learn which input triggers each case, why a team usually promises the worst case, and why the average depends on a guess about the data. The lesson on counting steps and Big-O covers the notation itself, and the lesson on hash table costs goes deeper into how the table is built. Here we only need to see which input causes which case.
Counting work so the cases can be compared
To compare cases we need a number. We will count the comparisons each algorithm makes. A comparison is one step where the program asks "is this value the one I want?" or "is this value smaller than that one?". Counting comparisons is a simple way to measure work, because most of the time goes into comparisons and moving data around.
The counts below come from real runs of Python code on the same machine. The numbers are exact counts, so they do not change from run to run. Timing in seconds would change with the machine, which is why we count instead.
Linear search: three inputs, three answers
Linear search looks at the items one at a time, from the first to the last, until it finds the target or runs out of items. It needs no sorted data. Here is a version that counts its comparisons and returns the position it found, or -1 if the target is missing.
best (target first): (0, 1)
worst (target last): (7, 8)
worst (target absent): (-1, 8)
average over every position: 4.5Read each line of output as a pair. The first number is the position found, and the second is the number of comparisons.
The best case is the input that finishes first. Here it is the target "10", which sits at position 0. The loop makes one comparison and stops. In general, the best case for linear search is a target at the front of the list. The work does not depend on the size of the list at all, because the search stops right away.
The worst case is the input that makes the search do the most work. There are two inputs that do this. One is a target at the very end of the list, which needs all 8 comparisons. The other is a target that is not in the list at all, which also needs all 8 comparisons, because the search must read every item before it can say "not found". For a list of n items, the worst case is n comparisons.
The average case needs an assumption. If the target is equally likely to be at any position, every position counts the same. The counts for positions 0 to 7 are 1, 2, 3, 4, 5, 6, 7 and 8, and their average is 4.5. In general, for a target that is in the list and equally likely to be in any position, the average is about half the list length, which is (n + 1) divided by 2 comparisons. If you know the target is usually near the front, for example because the most popular names are stored first, the real average is lower. If the target is usually missing, the real average is close to the worst case.
Here is how the worst case grows as the list grows. Each line is a search for a value that is not in the list.
n = 1000 absent target, comparisons: 1000
n = 2000 absent target, comparisons: 2000
n = 4000 absent target, comparisons: 4000Doubling the list doubles the worst case. That is the first real pattern in this lesson: for linear search, the worst case grows in step with the list length.
Quicksort: the input decides the shape
Quicksort is a sorting method. It picks one item as the pivot, which is the item the others are compared against. It then splits the rest into a smaller group and a larger group, and sorts each group the same way. The cost depends on how even the splits are, and the splits depend on which item is chosen as the pivot.
In the version below the pivot is always the first item. Each comparison is one item checked against the pivot.
sorted input, n = 100 comparisons: 4950
sorted input, n = 200 comparisons: 19900
sorted input, n = 400 comparisons: 79800
random input, n = 100 comparisons: 610
random input, n = 200 comparisons: 1434
random input, n = 400 comparisons: 3426Look at the sorted input first. When the list is already in order, the first item is always the smallest. Every split puts everything into the larger group and leaves the smaller group empty. The pivot is removed each time, but the split does not divide the work. The first level compares 99 items, the next compares 98, and so on. The total is 99 + 98 + ... + 1, which is 4950 for n = 100. Doubling the input from 100 to 200 makes the count about four times bigger, and doubling again makes it about four times bigger again. That growth pattern is the worst case for this version of quicksort.
For n items, the worst case is about n times n divided by 2 comparisons. The exact formula is n times (n minus 1) divided by 2. For n = 8, that is 28 comparisons. A sorted input of 8 items is the input that triggers this worst case.
The random input behaves very differently. The counts for random data grow slowly, and 400 random items need only 3426 comparisons, while 400 sorted items need 79800. The first item of random data is as likely to be near the middle as anywhere else, so the splits are roughly even. Each level of splitting does about n comparisons, and there are about log base 2 of n levels. Log base 2 of n is how many times you can halve n before it reaches 1. The shape of the work is n times log n, which is the best case for this kind of sort.
The best case is the input that makes every split even. The next program uses the middle value of each group as the pivot. It is run on the sorted input, which would be the worst case for the first-item pivot.
middle pivot, sorted input, n = 100 comparisons: 480
middle pivot, sorted input, n = 200 comparisons: 1153
middle pivot, sorted input, n = 400 comparisons: 2698The same sorted data now needs about 2700 comparisons for 400 items, instead of 79800. The data did not change. Only the choice of pivot changed. This is the core lesson of quicksort: the input and the pivot rule together decide the case you get.
In practice, sorting code does not promise the best case, because no pivot rule gives even splits for every input. Well-built sorts choose pivots so that the bad inputs are unlikely.
Hash lookup: usually constant, sometimes a crowd
A hash table stores each key in a slot chosen from the key's hash code. A hash code is a number computed from the key, and in Python the built-in hash function does it. To find a key, the table computes its hash, goes to that slot, and checks the key there. If the slot holds a different key with the same hash code, the table has a collision and must look at more slots. Collisions are the reason hash lookup is not always instant.
Here is a key class where every key has the same hash code. Every lookup has to compare the target with every other key that landed in the same slot. The class counts how many times Python asks whether two keys are equal.
all keys collide, n = 100 equality checks: 100 result: 99
all keys collide, n = 200 equality checks: 200 result: 199
all keys collide, n = 400 equality checks: 400 result: 399The number of checks equals the number of keys. This is the worst case for a hash lookup. Every key is in one slot, so the table behaves like a list that you have to search through from start to finish.
Now the normal case, where the hash codes spread the keys across slots.
spread keys, n = 100 lookup result: 99
spread keys, n = 200 lookup result: 199
spread keys, n = 400 lookup result: 399The output shows the answers but not the work. Python does not expose a comparison counter for its own dictionary, so we will not claim a count for this run. What matters is the design. With good hash codes, most keys sit alone in their slot, and a lookup usually checks one slot and stops. The average case is a small, fixed amount of work per lookup, no matter how many keys there are. We call that constant time.
The best case is the simplest of the three. The key is in its first slot, so the lookup makes one check. The average case assumes the hash codes spread keys out well, which good hash functions aim to do. The worst case is the crowd shown above, where every key shares one slot and a lookup may check all n keys.
Hash tables are fast because the average case is so good, but a program that depends on the average can still meet the worst case. A common cause is keys whose hash codes are poor, for example a class whose hash ignores most of its fields. The fix is to make the hash use every field that makes two keys different.
Which case to quote, and why
Each algorithm has its three cases, and a team has to choose which one to write down when it describes the speed of a feature. The usual choice is the worst case, for three reasons.
The first reason is that the worst case is a promise that holds for every input. If a service says "a lookup takes at most this much work", no user can receive a slower answer. The average case promises only that most requests are fast, and some user will always be in the slow part.
The second reason is that the worst case is often triggered by real input, not by a rare accident. A sorted list is a common input. Logs, timestamps and ids often arrive in order. A quicksort that picks the first item as its pivot will hit its worst case on that data, every time. Someone who thinks about the average only, and forgets the sorted input, will be surprised.
The third reason is that the average depends on a guess. The average linear search count, (n + 1) divided by 2, is correct only if the target is equally likely to be anywhere in the list. If your users search for the same few names over and over, the real average can be far from that figure. The worst case does not depend on a guess about the users.
The average case still has its uses. It describes what you expect when you have good data about the inputs, and it is useful for planning cost on a typical day. A good engineer writes both: the worst case as the promise, and the average case as the expected experience, with the assumption stated in words.
Common mistakes
Quoting the best case as the speed. A linear search that found its target at the first position once in a test is not evidence that searches are fast. The first check passes only when the target happens to be first. Test with the target last and with the target missing as well.
Forgetting the missing-target case. Many people think of the worst case as "the target is at the end". A target that is absent is just as bad for linear search, because the loop still reads every item. Here the search returned -1 only after 8 comparisons.
Assuming quicksort is always fast. A quick test with random numbers can make quicksort look like n times log n. If the input is already sorted and the pivot is the first item, the same function does about n times n divided by 2 work. Check the input shape before you trust a timing.
Treating hash lookup as always constant time. The average is constant only when the hash codes spread keys across slots. A class whose hash returns the same number for every key turns the table into a line of keys, and a lookup then costs about as much as a linear search.
Calling the average a guarantee. The average tells you about the typical case under an assumption. It does not promise that a single request will be fast. If one user in a thousand gets the worst case, the average can look fine while that user waits.
In Python, an error from a call that expects a value to be present looks like this, and it is a sign the search did not find the target:
Traceback (most recent call last):
File "<stdin>", line 2, in <module>
ValueError: list.index(x): x not in listThe index method searches from the front, just like the loop above, and it raises an error when nothing matches. The message above comes from Python 3.14, and older versions word it differently. A search that returns a position or -1 is a clearer design when the caller must handle a missing item.
Practice
Exercise 1. A list holds 50 names. Give an input that makes linear search do 1 comparison, one that makes it do 50, and the average number of comparisons for a name that is in the list, if every name is equally likely to be searched for.
Show the answer
One comparison happens when the target is the first name. Fifty comparisons happen when the target is the last name or when the target is missing. For a name that is in the list and equally likely to be any of the 50, the average is (50 + 1) divided by 2, which is 25.5 comparisons.
Exercise 2. A list has 8 items. The target appears twice, at position 2 and at position 6. Linear search stops at the first match. How many comparisons does it make?
Show the answer
It makes 3 comparisons. It checks position 0, position 1 and position 2, finds the target at position 2, and stops. Position 6 is never reached.
Exercise 3. Using the quicksort from this lesson with the first item as the pivot, how many comparisons does it make on a sorted input of 8 items? Use the formula from this lesson and check it with a run if you can.
Show the answer
It makes 28 comparisons. The formula is n times (n minus 1) divided by 2, which is 8 times 7 divided by 2, or 28. The first level compares 7 items, the next 6, and so on down to 1. The run for n = 100 gave 4950, which matches 100 times 99 divided by 2.
Exercise 4. A hash table holds 1000 keys, and every key has the same hash code. Roughly how many equality checks does one lookup of the last key inserted make? Explain why.
Show the answer
About 1000 checks. Every key sits in the same slot, so the lookup must compare the target with each key in that slot. The run with 400 colliding keys made 400 checks for the last key, which is the same pattern.
Exercise 5. A teammate says, "Our search is fast, it took 2 comparisons in my test." Write two sentences you could send back that ask the right question and name the case that matters.
Show the answer
One possible reply: "Which input did you test with? If the target was near the front, 2 comparisons is the best case, and I want to see the worst case, which is a target at the end or a target that is missing."
Summary
- The best case is the input that makes the work smallest. The worst case is the input that makes it largest. The average case is the expected work under a stated assumption about the inputs.
- In linear search, a target at the front is the best case, and a target at the end or a missing target is the worst case. The average for a target in the list is about half the list length.
- Quicksort with the first item as the pivot hits its worst case on sorted input, with about n times n divided by 2 comparisons. Random input and a middle pivot give about n times log n.
- A hash lookup is fast on average when keys spread across slots. When every key shares one slot, a lookup checks every key, and the cost matches a linear search.
- Teams usually promise the worst case, because it holds for every input and because real data, such as sorted lists, can trigger it.