DEV Community

Amon Olimov
Amon Olimov

Posted on

We're usually talking about the "worst case"

We're usually talking about the "worst case"

Often this "worst case" stipulation is implied. But sometimes you can impress your interviewer by saying it explicitly.

Sometimes the worst case runtime is significantly worse than the best case runtime:

  def contains(haystack, needle):
    # Does the haystack contain the needle?
    for item in haystack:
        if item == needle:
            return True
    return False

Here we might have 100 items in our haystack, but the first item might be the needle, in which case we would return in just 1 iteration of our loop.

In general we'd say this is O(n)O(n)O(n) runtime and the "worst case" part would be implied. But to be more specific we could say this is worst case O(n)O(n)O(n) and best case O(1)O(1)O(1) runtime. For some algorithms we can also make rigorous statements about the "average case" runtime. 
Enter fullscreen mode Exit fullscreen mode

Top comments (0)