Comparing complexities

Order O(1), O(log n), O(n), O(n log n), O(n^2) from fast to slow.

Big-O values from fast to slow: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n). O(1) is fastest.

O(1) runs in constant time regardless of input. O(n^2) quadruples when input doubles.

Worst and best case

An algorithm's worst case is the longest-running input; its best case is the shortest-running input.

In linear search, if the target is first the best case is O(1); if last, the worst case is O(n). Big-O usually denotes the worst case.

Write count_items(arr). Count elements with for and return. Print 3 with print(count_items([4, 5, 6])).

Show example solution

def count_items(arr):
    # Count items
    count = 0
    for x in arr:
        count = count + 1
    return count
print(count_items([4, 5, 6]))

Worst case

Big-O usually denotes the ____ case.

Show answer

Big-O usually denotes the worst case.