Big-O definition

Learn that Big-O is an upper bound with O(1), O(n), O(n^2) examples.

Big-O notation describes the upper bound of an algorithm's worst-case runtime. O(n) is linear, O(n^2) is quadratic growth.

Big-O ignores constant factors and lower-order terms; it keeps only the fastest-growing term. For example 3n + 5 becomes O(n).

Common Big-O values

Most common Big-O values, fast to slow: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) merge sort, O(n^2) quadratic.

This order is a key guide when choosing the right algorithm for a task. On large inputs, lower Big-O always wins.

Write first_element(arr). Return the first element. Print 7 with print(first_element([7, 3, 9])).

Show example solution

def first_element(arr):
    # Return first element
    return arr[0]
print(first_element([7, 3, 9]))

Big-O upper bound

Big-O represents the ____ of the worst case.

Show answer

Big-O represents the upper bound of the worst case.