🎓 A1Learner
🔍
0 of 100 lessons completed

DSA Best and Worst Cases

Best case and worst case are the inputs that make one program do the least work and the most work. Interviews grade the worst case, because that promise holds for every input.

A lucky first hit

This search checks items one by one and counts each check. The target sits first, so one comparison ends the search.

def count_search(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return comparisons
    return comparisons

words = ["ant", "bee", "cat", "dog", "elk"]
print(count_search(words, "ant"))

An unlucky last hit

The same code now hunts the last item. All five values are checked before the match appears.

def count_search(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return comparisons
    return comparisons

words = ["ant", "bee", "cat", "dog", "elk"]
print(count_search(words, "elk"))

A miss costs the full scan

A missing target can never end the search early. The count matches the last-hit count, because every item is checked.

def count_search(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return comparisons
    return comparisons

words = ["ant", "bee", "cat", "dog", "elk"]
print(count_search(words, "fox"))

Example

def search(values, target):
    comparisons = 0
    for value in values:
        comparisons += 1
        if value == target:
            return comparisons
    return comparisons

queue = ["Mia", "Leo", "Zoe", "Sam", "Amy", "Tom", "Eve"]
print("First hit:", search(queue, "Mia"))
print("Last hit:", search(queue, "Eve"))
print("Miss:", search(queue, "Rob"))

Key points

  • Best case: the input that lets the code finish with the least work
  • Worst case: the input that forces the code to do the most work
  • Average case: the typical work over many mixed inputs
  • One program can earn very different counts from different inputs

In this example, one search function runs three times on a queue of seven names. The first name is found after a single comparison. The last name needs all seven comparisons. The missing name also needs seven, because the search must rule out every name before answering. The worst count on this list is seven, and that is the count an interview answer would quote.

Note

Big O labels in this course describe the worst case unless a lesson says otherwise.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why do interviews grade the worst case?