Best, Average, and Worst-Case Time Complexity Explained

This article is part of the Data Structures & Algorithms with Python roadmap, and it’s the right place to start if you’re new to analyzing code efficiency.

Table of Contents

Toggle

You already know what Big O notation is. You know that O(n) means the work grows with the input, and O(log n) means the work shrinks fast. But here’s something that trips up almost every beginner.

The same algorithm can have different Big O values, depending on the situation.

Look at linear search. If the value you’re looking for is the very first item, you find it instantly. If it’s the last item, or it isn’t there at all, you have to check everything. Same algorithm. Same code. Two very different outcomes.

This is where best case, average case, and worst case come in. They answer a question Big O alone doesn’t answer: which situation are we actually talking about?

This guide is for anyone who has learned Big O basics and wants the next layer of understanding, especially if you’re preparing for coding interviews. By the end, you’ll know exactly what best, average, and worst case mean, how to spot them in real code, and how to explain them the way interviewers expect.

In Simple Terms

Best, average, and worst case describe which input you’re analyzing. Best case is the easiest possible input. Worst case is the hardest possible input. Average case is what you’d expect across many typical inputs. Big O notation can then be used to describe the growth rate of any one of these three situations.

What Is Best-Case Complexity?

Let’s start with an example.

Imagine you’re looking for your keys on a table full of stuff. Best case, they’re the very first thing you spot. You reach out, grab them, and you’re done in one second.

That’s best-case performance. It’s what happens when the input is as favorable as possible for the algorithm.

In code, best-case complexity describes the fewest steps an algorithm will ever need, given the most convenient possible input.

Here’s linear search in Python:

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

If target happens to be numbers[0], the loop runs exactly once. It doesn’t matter if the list has 10 items or 10 million items. One check, and we’re done.

That gives linear search a best case of:

O(1)

Why best case rarely matters much

Here’s the catch. Best case sounds great, but it’s usually the least useful number to know.

Why? Because you rarely get to control which input you’ll receive. If you’re building a search feature for an app, you can’t promise your users that what they’re looking for will always be first in the list. Most of the time, it won’t be.

Best case is worth knowing so you understand the full picture. But it’s rarely the number you’d use to make a real decision about an algorithm.

What Is Average-Case Complexity?

Now let’s go back to the table full of stuff.

On a normal day, your keys aren’t always the first thing you see, and they’re not always buried at the very bottom either. Most of the time, you find them somewhere in the middle, after moving a few things around.

That’s the idea behind average case. It’s what typically happens, across many realistic attempts, rather than the best possible attempt or the worst possible one.

For linear search, if the target is equally likely to be anywhere in the list, then on average, you’d expect to check about half the list before finding it.

For a list of n items, that’s roughly:

n / 2

And in Big O terms, constants get dropped, so:

O(n)

Notice something important here. The average case for linear search is still O(n), the same as the worst case. The number of steps you take on an average day is smaller than the worst day, but the growth rate is the same. If the list gets 10 times bigger, your average search time also gets roughly 10 times bigger, just like the worst case does.

Why average case is tricky to calculate

Average case sounds simple, but it depends heavily on assumptions about the input. What does “average” even mean here?

• Is every item in the list equally likely to be the target?
• Could the data have patterns, like being partially sorted already?
• Are we averaging across random inputs, or across the inputs your actual users will send?

This is why average-case analysis is used less often in everyday interviews and more often in academic algorithm analysis, where the assumptions are stated clearly upfront. In practice, most engineers lean on worst case instead, because it doesn’t require guessing about the shape of future input.

What Is Worst-Case Complexity?

Now, the least convenient scenario. Your keys are at the very bottom of the pile, underneath everything else. You have to move every single item before you find them.

That’s worst case. It describes what happens with the least favorable input possible.

For linear search, the worst case happens when the target is the last element, or when it isn’t in the list at all:

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

If target isn’t found, the loop has to run through every single item before returning -1. That’s n checks.

Worst case for linear search:

O(n)

Why worst case gets so much attention

Worst case is the number developers talk about the most, and for a good reason: it’s a guarantee.

If someone tells you an algorithm is O(n) in the worst case, you know for certain it will never take longer than that, no matter how unlucky the input is. That’s a promise you can actually build software around.

Think about it from a different angle. Imagine you’re designing the search feature for a hospital’s patient record system. You don’t get to hope the doctor’s search term happens to match an early record. You need to know the absolute upper bound on how long that search could ever take, because someone’s care might depend on it.

That’s why, when someone casually says “this algorithm is O(n)” without specifying which case, they almost always mean the worst case. It’s the most useful default assumption in engineering.

Why Worst Case Matters in Interviews

If you’re preparing for coding interviews, here’s something worth remembering: when an interviewer asks “what’s the time complexity of your solution,” they are almost always asking about the worst case, unless they say otherwise.

There are a few reasons this matters so much in an interview setting.

1. It shows you’re thinking about guarantees, not luck

Anyone can write code that works on the example the interviewer gave you. What separates a strong answer is showing you understand what happens when the input is uncooperative. Interviewers want to hear you say something like, “In the worst case, this runs in O(n²), because for every element, I’m scanning the rest of the list.”

2. It reveals whether you understand your own code

Some candidates write correct code but can’t explain why it behaves a certain way under different inputs. Being able to say, “the best case here is O(1) if the target is at the start, but the worst case is O(n) if it’s missing entirely,” proves you actually understand the mechanics, not just the syntax.

3. It sets up the next question

Almost every interview follows this pattern:

1. Write a working solution.
2. State its time and space complexity, usually worst case.
3. Get asked, “Can you do better?”

If you can’t state the worst case clearly in step 2, you can’t meaningfully answer step 3.

Linear Search Example

Let’s put all three cases side by side using the same function.

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

def linear_search(numbers, target):
    for index, value in enumerate(numbers):
        if value == target:
            return index
    return -1

Notice the pattern. Best case is the outlier here, dramatically better than the other two. Average and worst case share the same Big O, even though the average case does fewer actual steps in practice.

This is common for simple algorithms like linear search: best case is a special situation, while average and worst case grow the same way.

Binary Search Example

Binary search behaves differently, and it’s a great example of why “best case” isn’t always trivial to spot.

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2

        if numbers[middle] == target:
            return middle
        elif numbers[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2

        if numbers[middle] == target:
            return middle
        elif numbers[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Best case

The best case happens when the target is exactly at the middle of the sorted list. The very first comparison finds it, and we’re done.

O(1)

Worst case

The worst case happens when the target is nowhere near the middle, or isn’t in the list at all. Each step still cuts the remaining search space in half, so the number of steps grows very slowly, but it does grow.

O(log n)

Average case

On average, across many different target values, most searches will need somewhere between 1 and log n steps. When you work out the math, the average case still comes out to:

O(log n)

Here’s the interesting part. Even though binary search’s best case (O(1)) and worst case (O(log n)) are technically different, in practice almost everyone just says “binary search is O(log n).” That’s because O(log n) already grows so slowly that the gap between best and worst case barely matters for real-world performance. The distinction that actually changes how you’d talk about the algorithm is: sorted data, and cutting the space in half. Not the rare lucky first guess.

Sorting Algorithm Examples

Sorting is where best, average, and worst case really start to matter for real engineering decisions, because different sorting algorithms behave very differently depending on the input.

Bubble Sort

Bubble Sort repeatedly compares neighboring elements and swaps them if they’re out of order.

def bubble_sort(numbers):
    n = len(numbers)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers

def bubble_sort(numbers):
    n = len(numbers)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers

• Best case: the list is already sorted. The inner loop finds no swaps at all, swapped stays False, and the function exits after a single pass. That gives us O(n).
• Worst case: the list is sorted in reverse order. Every element has to bubble all the way to its correct position, requiring nested passes over almost the entire list. That gives us O(n²).
• Average case: for a randomly shuffled list, you still end up doing roughly the same nested comparisons as the worst case. That gives us O(n²).

This is a great example of a huge best-to-worst gap. One extra check (if not swapped: break) turns an already-sorted list into a fast O(n) pass, while a reverse-sorted list still crawls through O(n²).

Quick Sort

Quick Sort picks a pivot value, then partitions the list into elements smaller and larger than the pivot, recursively sorting each side.

• Best and average case: when the pivot splits the list into two roughly equal halves each time, the recursion depth is about log n, and each level does O(n) work. That gives us O(n log n).
• Worst case: if the pivot is consistently the smallest or largest element (which can happen with already-sorted data and a naive pivot choice), the list barely gets split at all. Each recursive call only shrinks the problem by one element instead of by half. That gives us O(n²).

This is exactly why real-world Quick Sort implementations use tricks like picking a random pivot or the median of three values. It’s a direct defense against hitting that worst case.

Merge Sort

Merge Sort always splits the list exactly in half, then merges the sorted halves back together.

• Best, average, and worst case: all three are O(n log n). The split always happens evenly, no matter what the input looks like, so there’s no unlucky input that makes it behave worse.

This consistency is Merge Sort’s biggest selling point. You lose the chance at a lucky O(n) best case like Bubble Sort gets on sorted data, but you gain a guarantee: it will never degrade to O(n²), no matter what you throw at it.

This table alone explains why Merge Sort is often preferred when consistency matters, while Quick Sort is often preferred when average speed matters more than worst-case guarantees, since its typical performance is very fast in practice.

Big O vs Big Theta vs Big Omega

You’ll sometimes see two other symbols alongside Big O: Big Omega (Ω) and Big Theta (Θ). They aren’t extra difficulty for its own sake. They exist to make a specific distinction precise.

• Big O (O) describes an upper bound. It says, “this algorithm will never do more work than this, as the input grows.” It’s a ceiling.
• Big Omega (Ω) describes a lower bound. It says, “this algorithm will never do less work than this.” It’s a floor.
• Big Theta (Θ) describes a tight bound, meaning the upper and lower bounds match. It says, “this algorithm’s growth is exactly this, not just at most this or at least this.”

Here’s an example that makes the difference concrete. For linear search on an unsorted list:

• The worst case is Θ(n), because it’s both the ceiling and the floor. It will do exactly n work when the target is missing, no more, no less.
• But if we’re talking generally about linear search across best, average, and worst cases combined, we can only say it’s O(n), because we can’t guarantee a tight bound across every situation.

In casual conversation, developers almost always just say “Big O,” even when they technically mean a tight bound. That’s not really wrong; it’s a widely accepted convention. Big O has become the everyday shorthand for describing growth rate, regardless of whether the bound is tight or just an upper limit.

You don’t need to actively use Big Omega or Big Theta in your day-to-day coding. But recognizing them if you see them in a textbook, a course, or an interview question means you won’t get thrown off by unfamiliar notation for a concept you already understand.

How Interviewers Expect You to Explain Complexity

Let’s make this practical. Here’s what a strong answer sounds like when an interviewer asks about your solution’s complexity, compared to a weak one.

Weak answer:

“It’s O(n).”

This isn’t wrong, but it doesn’t show any depth. It doesn’t tell the interviewer whether you understand why, or whether you’ve thought about different inputs at all.

Strong answer:

“In the best case, if the target is near the start, this finishes almost immediately. But I should assume the worst case for planning purposes, which happens when the target is missing or near the end. In that case, we check every element once, so it’s O(n) time and O(1) space.”

Notice the structure of that answer:

1. Acknowledge that best, average, and worst case can differ.
2. State clearly which case you’re defaulting to (usually worst case) and why.
3. Explain why that case produces that specific complexity, not just the label.
4. Mention space complexity too, since interviewers often expect both.

A simple habit to build

Whenever you finish writing a solution in an interview, try saying this out loud, even if no one asked yet:

“The worst case here is O(___), because . The best case would be O(), if ___.”

Filling in those blanks forces you to actually think through the input space, instead of pattern-matching a label onto your code. It’s a small habit, but interviewers notice the difference immediately.

FAANG-Style DSA Interview Questions

These are the kinds of time-complexity questions you may encounter in DSA interviews at companies such as Google, Amazon, Meta, Microsoft, and similar technology companies.

1. What is the time complexity of linear search?

Answer:
Best case: O(1) when the target is the first element.
Average case: O(n) when the target can appear at any position.
Worst case: O(n) when the target is at the end or does not exist.

2. What is the time complexity of binary search?

Answer:
Best case: O(1) when the middle element is the target.
Average case: O(log n).
Worst case: O(log n).

Binary search requires the input to be sorted.

3. Why is binary search O(log n)?

Answer:
Each comparison eliminates roughly half of the remaining search space. After one comparison, n becomes about n/2, then n/4, then n/8, and so on. The number of steps therefore grows logarithmically with the input size.

4. What is the best-case time complexity of Bubble Sort?

Answer:
With an early-exit optimization, Bubble Sort has a best-case complexity of O(n) when the array is already sorted and a complete pass makes no swaps.

Its average and worst-case complexity is O(n²).

5. What is the worst-case time complexity of Quick Sort?

Answer:
O(n²).

This can happen when the pivot repeatedly produces highly unbalanced partitions, such as when a naive implementation consistently chooses a poor pivot.

6. What is the average-case complexity of Quick Sort?

Answer:
O(n log n), assuming reasonably balanced partitions on average.

The exact behavior depends on the pivot-selection strategy and the input distribution.

7. Why does Merge Sort have O(n log n) complexity in all three cases?

Answer:
Merge Sort repeatedly divides the input into smaller pieces, creating about log n levels of recursion. At each level, the algorithm processes all n elements during merging.

Therefore, the best, average, and worst cases are all O(n log n).

8. An algorithm is O(n). Does that mean it always performs exactly n operations?

Answer:
No.

Big O describes an asymptotic upper bound on how the work grows. An O(n) algorithm could perform 2n operations, n + 10 operations, or another amount that grows linearly.

Big O is about the growth rate, not an exact operation count.

9. Which case should you give when an interviewer asks for the time complexity?

Answer:
Clarify the case when it matters.

For example:

“The best case is O(1), while the average and worst cases are O(n).”

If the interviewer simply asks for “the time complexity,” worst-case complexity is commonly reported, but stating the relevant cases shows a better understanding of the algorithm.

10. Can an algorithm be O(n) and O(n²) at the same time?

Answer:
Yes.

If an algorithm is O(n), it is technically also O(n²), because n grows no faster than n². However, O(n) is the tighter and more useful upper bound.

11. What is the difference between Big O, Big Omega, and Big Theta?

Answer:

• Big O: asymptotic upper bound
• Big Omega (Ω): asymptotic lower bound
• Big Theta (Θ): asymptotically tight bound

For example, linear search has a best-case complexity of Θ(1) and a worst-case complexity of Θ(n).

12. Why do interviewers ask for best, average, and worst-case complexity?

Answer:
Because the same algorithm can behave very differently depending on the input.

For example, linear search can find the target immediately in O(1), while searching an entire list can take O(n).

Understanding these cases helps you explain not just how an algorithm works, but how its performance changes with different inputs.

A Good Interview Answer Pattern

When explaining an algorithm in an interview, use this simple structure:

Best case: O(?)
Average case: O(?)
Worst case: O(?)
Why: Explain what happens to the input as the algorithm runs.

For example:

“For binary search, the best case is O(1) when the middle element is the target. The average and worst cases are O(log n) because each comparison cuts the search space roughly in half.”

Practice Problems

Try solving these problems before checking the answers. The goal is not only to identify Big O, but to determine which case you are analyzing.

Problem 1: Find an Element

Given a list of n numbers, search for a target value using linear search.

def find_value(numbers, target):
    for number in numbers:
        if number == target:
            return True
    return False

def find_value(numbers, target):
    for number in numbers:
        if number == target:
            return True
    return False

What is the:

• Best-case time complexity?
• Average-case time complexity?
• Worst-case time complexity?

Problem 2: Search a Sorted List

A sorted list contains n elements. You use binary search to find a target value.

What is the:

• Best-case time complexity?
• Average-case time complexity?
• Worst-case time complexity?

Why does the input need to be sorted?

Problem 3: Count the Operations

What is the time complexity of this code?

def process(numbers):
    for number in numbers:
        print(number)

    for number in numbers:
        print(number)

def process(numbers):
    for number in numbers:
        print(number)

    for number in numbers:
        print(number)

Is it O(n), O(2n), or something else?

Problem 4: Nested Loops

Determine the time complexity:

def compare(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            print(numbers[i], numbers[j])

def compare(numbers):
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            print(numbers[i], numbers[j])

What happens to the number of operations when n doubles?

Problem 5: Early Exit

Consider this search:

def contains_duplicate(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] == numbers[j]:
                return True
    return False

def contains_duplicate(numbers):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] == numbers[j]:
                return True
    return False

Determine the:

• Best-case complexity
• Worst-case complexity

What input produces the best case?

Problem 6: Bubble Sort

Assume Bubble Sort stops early when a complete pass makes no swaps.

What are its:

• Best-case complexity?
• Average-case complexity?
• Worst-case complexity?

What type of input produces the best case?

Problem 7: Quick Sort

Quick Sort uses the first element as its pivot.

What can happen when the input is already sorted?

What are the:

• Best-case complexity?
• Average-case complexity?
• Worst-case complexity?

Problem 8: Identify the Complexity

Match each complexity with the situation:

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n²)

A. Checking every element in a list once
B. Looking up an element by index in a Python list
C. Binary search
D. Comparing every pair of elements
E. Merge Sort

Problem 9: Big O or Big Theta?

An algorithm performs between 3n and 5n operations as n grows.

What is the tight asymptotic complexity?

Is it:

• O(n)
• Ω(n)
• Θ(n)
• All three

Explain your answer.

Problem 10: Interview Challenge

An interviewer gives you an algorithm with the following behavior:

• It checks one element at a time.
• It may find the target immediately.
• If the target is near the end, it checks most of the input.
• If the target does not exist, it checks the entire input.

Without writing code, describe its:

• Best-case complexity
• Average-case complexity
• Worst-case complexity

Then explain what assumption you would make when discussing the average case.

Answers

1. Linear Search

Best: O(1)
Average: O(n)
Worst: O(n)

2. Binary Search

Best: O(1)
Average: O(log n)
Worst: O(log n)

The list must be sorted so that each comparison can eliminate roughly half of the remaining search space.

3. Count the Operations

O(n).

Two passes give approximately 2n operations, but constant factors are ignored in asymptotic notation.

4. Nested Loops

O(n²).

The outer loop runs n times and the inner loop also runs up to n times.

5. Early Exit

Best: O(1)
Worst: O(n²)

The best case occurs when a duplicate is found immediately.

6. Bubble Sort

Best: O(n) with early exit
Average: O(n²)
Worst: O(n²)

The best case occurs when the list is already sorted.

7. Quick Sort

Best: O(n log n)
Average: O(n log n)
Worst: O(n²)

With the first element always chosen as the pivot, already sorted input can produce highly unbalanced partitions and lead to the worst case.

8. Complexity Matching

A. O(n)
B. O(1)
C. O(log n)
D. O(n²)
E. O(n log n)

9. Big O or Big Theta?

Θ(n).

Because the number of operations has both an asymptotic upper bound and lower bound proportional to n, the tight bound is Θ(n). It is also technically O(n) and Ω(n).

10. Interview Challenge

Best: O(1)
Average: O(n), assuming the target is equally likely to occur at any position
Worst: O(n)

This describes linear search.

Frequently Asked Questions

Conclusion

Big O tells you how work grows. Best, average, and worst case tell you which situation you’re measuring that growth for. The two ideas work together: an algorithm doesn’t have one single Big O value locked in forever. It has a best case, an average case, and a worst case, and each one can tell a completely different story about the same piece of code.

The habit worth building from here: whenever you calculate a complexity, ask yourself which case you’re actually describing. Then default to worst case unless you have a good reason not to, since that’s the number that gives you a real guarantee.

If you haven’t already, the Big O notation guide covers the foundational ideas this article builds on. And for the complete learning path, the DSA with Python guide lays out where to go next.

From here, the next article in this series looks at recursion in Python, and how the call stack shapes both the time and space complexity of recursive solutions

Further Reading

If you want to explore time complexity and algorithm analysis in more detail, these resources are useful:

• Python Documentation: Time Complexity of Built-in Types
  https://docs.python.org/3.16/library/time-complexity.html
• University of San Francisco: Data Structures and Algorithms
  https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• University of San Francisco: Big-O Notation
  https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• University of San Francisco: Algorithm Analysis
  https://www.cs.usfca.edu/~galles/visualization/Algorithms.html