Fast in the Demo, Slow for Users: Best, Worst and Average
Explain why a search that was instant in your demo is slow for users, name its best, worst and average cases, and see why Big-O usually promises the worst one.
Apprentice · Software Development · Updated
After this lesson you can
- Describe the best, worst and average case of searching a list from the top
- Explain why Big-O usually describes the worst case
Key takeaways
- The best case is the luckiest data for an algorithm, the worst case is the unluckiest, and the average case is what to expect most of the time.
- Searching a list from the top is 1 step at best, n steps at worst, and about n ÷ 2 on average, which is still O(n).
- Big-O usually describes the worst case, because that's the one you can promise.
- A demo that searches for the first song shows only the best case; users who search for songs near the end, or missing, meet the worst.
You show the music app's search to your team. You type Midnight Bus, and the answer appears before you lift your finger. A week after launch, users say search is slow. Same code, same phones. What changed? In the demo you searched for Midnight Bus, the first song on the playlist. Users search for songs anywhere on it, and very often for songs that aren't there at all. Your manager asks the question that matters: "How long does a search take, at most?"
What would you try?
Run the demo again. It's instant again, because it searches for the same first song. The demo only ever shows the luckiest day.
Time a few searches and average them. The answer depends on which songs you happened to pick: three songs near the top give one number, three near the end another. It can't promise anything.
Count the reads for the unluckiest song. A search that reads from the top can never read more than every title. That's a number you can promise, however the users search.
Same search, different songs
Here is the search from Why the Library Check Slows Down and Play Doesn't: O(1) and O(n), with a playlist of 8 songs. It looks for four titles: the first song, the one from your demo; a song in the middle; the last song; and Blue Hour, which isn't on the playlist.
List<string> playlist = new List<string> { "Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour" };
int TitlesRead(string title)
{
int reads = 0;
foreach (string song in playlist)
{
reads++;
if (song == title)
{
break;
}
}
return reads;
}
foreach (string title in new string[] { "Midnight Bus", "Paper Boats", "Golden Hour", "Blue Hour" })
{
Console.WriteLine(title + ": " + TitlesRead(title) + " of 8 titles read");
}
Midnight Bus: 1 of 8 titles read
Paper Boats: 4 of 8 titles read
Golden Hour: 8 of 8 titles read
Blue Hour: 8 of 8 titles read
List<String> playlist = List.of("Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour");
int titlesRead(String title) {
int reads = 0;
for (String song : playlist) {
reads++;
if (song.equals(title)) {
break;
}
}
return reads;
}
void main() {
for (String title : new String[] {"Midnight Bus", "Paper Boats", "Golden Hour", "Blue Hour"}) {
IO.println(title + ": " + titlesRead(title) + " of 8 titles read");
}
}
Midnight Bus: 1 of 8 titles read
Paper Boats: 4 of 8 titles read
Golden Hour: 8 of 8 titles read
Blue Hour: 8 of 8 titles read
playlist = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"]
def titles_read(title):
reads = 0
for song in playlist:
reads += 1
if song == title:
break
return reads
for title in ["Midnight Bus", "Paper Boats", "Golden Hour", "Blue Hour"]:
print(f"{title}: {titles_read(title)} of 8 titles read")
Midnight Bus: 1 of 8 titles read
Paper Boats: 4 of 8 titles read
Golden Hour: 8 of 8 titles read
Blue Hour: 8 of 8 titles read
const playlist = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"];
function titlesRead(title) {
let reads = 0;
for (const song of playlist) {
reads++;
if (song === title) {
break;
}
}
return reads;
}
for (const title of ["Midnight Bus", "Paper Boats", "Golden Hour", "Blue Hour"]) {
console.log(`${title}: ${titlesRead(title)} of 8 titles read`);
}
Midnight Bus: 1 of 8 titles read
Paper Boats: 4 of 8 titles read
Golden Hour: 8 of 8 titles read
Blue Hour: 8 of 8 titles read
const playlist: string[] = ["Midnight Bus", "Lemon Skies", "Slow Rain", "Paper Boats", "Neon Garden", "Quiet Harbor", "Sunday Static", "Golden Hour"];
function titlesRead(title: string): number {
let reads = 0;
for (const song of playlist) {
reads++;
if (song === title) {
break;
}
}
return reads;
}
for (const title of ["Midnight Bus", "Paper Boats", "Golden Hour", "Blue Hour"]) {
console.log(`${title}: ${titlesRead(title)} of 8 titles read`);
}
Midnight Bus: 1 of 8 titles read
Paper Boats: 4 of 8 titles read
Golden Hour: 8 of 8 titles read
Blue Hour: 8 of 8 titles read
The playlist sits outside the search, where the search can read it: a variable at the top of the program in C#, Python, JavaScript and TypeScript, and a field of the program in Java.
Same playlist, same code: 1 read for the demo's song, and all 8 for the last song and the missing one.
How it got its name
These three kinds of luck come up with every algorithm, so they have names:
- The best case is the luckiest data: the item is the first one you check. Your demo.
- The worst case is the unluckiest: the item is the last one you check, or it isn't there at all, so you check everything.
- The average case is what to expect over many tries: somewhere in the middle.
You know them from any morning when you're late and your keys are in one of eight pockets. Sometimes they're in the first pocket you check, sometimes in the last, and sometimes you check all eight and then remember they're on the table.

For any playlist of n songs:
| Case | When it happens | Titles read | Big-O |
|---|---|---|---|
| Best | the song is first | 1 | O(1) |
| Worst | the song is last, or not there | n | O(n) |
| Average | the song is somewhere in the list, any spot as likely as another | about n ÷ 2 | O(n) |
The average case is about half the playlist, n ÷ 2. By the rule in Are Two Loops Twice as Slow? Why O(2n) Is Still O(n), dividing by 2 doesn't change the growth: it's still O(n). Double the playlist and the average search doubles too.
Why Big-O usually means the worst case
When someone says "searching a list is O(n)", they mean the worst case, unless they say otherwise. There are three good reasons, and your manager's question is the first:
- The worst case is a promise. "It never reads more than n titles" is something you can count on. "It's usually fast" isn't.
- The best case is too lucky to plan around. Nearly any search is 1 step when the item happens to be first, which is why demos so often look fast.
- Users remember the slow day. A support line that's usually quick but sometimes keeps you waiting an hour is remembered for the hour.
A bus timetable works the same way when it's honest: it tells you the latest the bus will come, not the time it came on the luckiest day.
Try it. Add four more songs to the playlist and run the code again. The best case is still 1 title, and the worst case is now 12. Which song would you search for to see the average case, about 6 titles?
In your textbook
Your textbook or class may use two more symbols, Θ (big theta) and Ω (big omega), next to Big-O. They're not the names of the average and best cases, though people often mix them up. The lesson In Your Textbook: Big-O, Big-Θ and Big-Ω explains what each one says.
Check yourself
2 questions to try on the lesson page.
So what
When you compare two pieces of code, compare their worst cases first: it's the day that decides whether your app keeps its promises. Knowing the best and average cases too helps you explain why code that "seemed fast" in testing slowed down in real use, and to test with the songs your users will really search for.