Big-O Notation

Big-O notation describes an upper bound on how an algorithm’s cost grows with input size. In beginner algorithm practice, it is often used as a simplified language for growth rate.

Big-O hides constant factors and smaller terms so the main pattern is easier to see.

Core Idea

If an algorithm does about 3n + 10 basic operations, the important long-term pattern is linear growth, so it is described as O(n). If an algorithm checks every pair of elements, the main pattern is usually O(n^2).

Common growth rates include O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n).

Big-O is a way to talk about growth while ignoring details that do not change the large-scale shape. The exact expression 3n + 10 still grows linearly. The exact expression n^2 + n still grows quadratically.

The dominant term is the part that eventually matters most as input grows.

Example Contracts

print_pairs(values) accepts a sequence and prints every ordered pair. It is meant to show quadratic growth, not to be a practical output routine for large inputs.

first_value(values) accepts a non-empty sequence and returns the first element. It is constant time because it does not scan the rest of the input.

Python Example

def print_pairs(values):
    for left in values:
        for right in values:
            print(left, right)

If values has n elements, the inner print runs n * n times. The time complexity is O(n^2).

Another example:

def first_value(values):
    return values[0]

This is O(1) because it performs the same kind of direct index access regardless of how long the list is.

Growth Rates

A rough order from slower growth to faster growth is:

• O(1): constant.
• O(log n): grows by one step when the input roughly doubles.
• O(n): one pass over the input.
• O(n log n): common for efficient comparison sorting.
• O(n^2): all pairs or nested full scans.
• O(2^n): many subset or choice problems.

The difference becomes dramatic as n grows. For n = 1,000,000, log n is small, n is one million, and n^2 is one trillion.

Simplifying Expressions

When simplifying Big-O:

• Drop constant factors: O(3n) becomes O(n).
• Drop smaller terms: O(n^2 + n) becomes O(n^2).
• Keep different variables when they mean different input sizes: O(V + E) should stay O(V + E).
• Do not simplify O(n + q) to O(n) if q can grow independently.

Common Confusions

Big-O is not a measurement of exact runtime. It does not say how many milliseconds a program will take.

Big-O also does not automatically describe every case. A function can have one Big-O bound for its worst case and another for its best case.

Another common mistake is dropping the wrong variable. In graph algorithms, O(V + E) should not be simplified to O(n) unless n has been defined to include both vertices and edges.

Big-O also does not say an algorithm is always fast enough. O(n) can still be too slow if n is enormous and each step is expensive. It only describes growth shape.

When To Use It

Use Big-O when comparing algorithms at the level of growth. It is most useful when the input can become large enough that the growth pattern dominates small implementation details.

Use it after defining input size. A statement like “this is O(n)” should be paired with a clear meaning for n.

The Main Point

Big-O keeps the dominant growth pattern and ignores constant details. It is a tool for comparing scalability, not a precise runtime prediction.