1.1 What Is Complexity?

Define input size and the operation being counted, then ask how the work grows. Short Python 3 programs separate growth rates from exact step counts and elapsed time.

Separate the Three Concepts First

Introduction to complexity often conflates the following three ideas:

Term	How this chapter defines it	Example
Input size	A single or multiple variable describing how large the problem is	An array has n elements
Basic operation	A representative action chosen to count	One comparison, one element access
Growth rate	How the number of operations grows as input size increases	Θ(n), O(n²)

Before analyzing for value in values, it's important to clarify n = len(values). When analyzing two arrays, use n and m separately; unless explicitly stated otherwise, do not assume they are the same length and refer to both as n.

We typically adopt a simplified "unit-cost model": operations like array access, integer addition, and comparison each count as one step. This model is useful for observing growth trends, but it does not reflect the full picture of real hardware performance. Operations such as long string comparisons, hashing, large integer arithmetic, memory allocation, and I/O can have costs that are far from constant.

Your First Puzzle

The input is an array of n integer identifiers. Count the unordered pairs of positions whose identifier values are not adjacent; for example, 1 and 2 are invalid while 1 and 3 are valid. Define the input size and basic operation before comparing enumeration with an optimized approach.

def count_allowed_pairs(resources):
    count = 0
    for left in range(len(resources)):
        for right in range(left + 1, len(resources)):
            if abs(resources[left] - resources[right]) != 1:
                count += 1
    return count

The program checks n(n - 1)/2 position pairs, resulting in a time complexity that grows as Θ(n²), with auxiliary space of Θ(1). Equal identifiers are allowed because their difference is 0; duplicates count separately by position. Since the function returns only a count, we can subtract adjacent-value combinations from all position pairs:

from collections import Counter

def count_allowed_pairs_fast(resources):
    frequencies = Counter(resources)
    total = len(resources) * (len(resources) - 1) // 2
    adjacent = sum(count * frequencies.get(value + 1, 0)
                   for value, count in frequencies.items())
    return total - adjacent

assert count_allowed_pairs_fast([-1, 0, 0, 2]) == 4
assert count_allowed_pairs_fast([]) == 0

Each adjacent pair of values is counted once, from value to value + 1. With u distinct identifiers, unit-cost integer arithmetic, and the usual hashing assumptions, expected time is Θ(n) and auxiliary space is Θ(u). Listing every pair would require accounting for output costs too.

What Big O Actually Says

Big O describes an asymptotic upper bound. Intuitively, if an algorithm's work grows no faster than a constant multiple of g(n) as the input size increases, then we can write it as O(g(n)).

For example, consider a piece of code that performs 3n + 7 model operations:

• It is O(n), because for sufficiently large inputs, 3n + 7 is eventually bounded by some constant multiple of n;
• It is also a loose upper bound, or a "loose" O(n²);
• To more precisely express that the growth rate matches n, we should write Θ(n).

In everyday conversation, "Big O" is often used as a general term for algorithmic complexity. But don’t confuse it with "worst-case", that refers to the choice of input. Big O applies an upper bound to a chosen cost function. After completing typical code analyses, the third article will formally separate O, Ω, Θ from best, worst, and average-case scenarios.

Why We Can Ignore Constants and Lower-Order Terms

Suppose two approaches have the following workloads:

A(n) = 3n + 7
B(n) = n² + 2n + 1

As n grows larger, the dominant term in 3n + 7 is n, so we write Θ(n); the dominant term in n² + 2n + 1 is n², so we write Θ(n²).

This step is merely classifying growth trends. It does not mean that constants are always irrelevant, nor that two programs both with Θ(n) complexity will have identical actual runtime performance. When data sizes are small, constant factors differ significantly, or cache behavior varies, engineering outcomes must still be validated through measurement.

Seven Common Growth Rates

The expressions in the table below are used for comparing growth rates, not promises that a program will execute a specific number of instructions.

Growth Class	Common Name	Representative Expression	Typical Use Cases
Θ(1)	Constant	1	Accessing array elements by index
Θ(log n)	Logarithmic	⌊log₂ n⌋	Halving the search interval in each iteration
Θ(n)	Linear	n	Scanning all elements
Θ(n log n)	Linear Logarithmic	n log₂ n	Merge sort
Θ(n²)	Quadratic	n²	Checking all ordered element pairs
Θ(2ⁿ)	Exponential	2ⁿ	Visiting all subsets without copying members
Θ(n!)	Factorial	n!	Visiting all permutations without copying members

Copying every subset into its own list produces n·2^(n-1) elements in total. Copying every permutation produces n·n! elements. Output time and space then reach Θ(n·2ⁿ) and Θ(n·n!), respectively; counting leaves alone misses that cost.

A few useful interpretations:

• Constant time does not mean "only one statement is executed"; it means the number of operations does not grow with n.
• Logarithmic time arises from repeatedly reducing the problem size by a fixed ratio. The base of the logarithm only introduces a constant factor, so it's typically omitted in asymptotic notation.
• n log n grows by a slowly increasing factor compared to n, so it's incorrect to say they're essentially the same speed.
• Exponential and factorial growth are very rapid, but small inputs may still be practical. Whether a solution is viable depends on real-world constraints, rather than on the symbolic form alone.

Turn Growth Into Checkable Steps

The following code does not measure time. At n = 8, it explicitly executes five loop models and counts their operations: constant, logarithmic, linear, linear-logarithmic, and quadratic. This allows us to verify why each growth rate follows, without attributing a single machine's accidental performance to a general rule.

# growth_demo.py

def require_positive(n: int) -> None:
    if n <= 0:
        raise ValueError("n must be positive")

def constant_steps(n: int) -> int:
    require_positive(n)
    return 1

def logarithmic_steps(n: int) -> int:
    require_positive(n)
    steps = 0
    remaining = n
    while remaining > 1:
        remaining //= 2
        steps += 1
    return steps

def linear_steps(n: int) -> int:
    require_positive(n)
    steps = 0
    for _ in range(n):
        steps += 1
    return steps

def linearithmic_steps(n: int) -> int:
    require_positive(n)
    steps = 0
    for _ in range(n):
        remaining = n
        while remaining > 1:
            remaining //= 2
            steps += 1
    return steps

def quadratic_steps(n: int) -> int:
    require_positive(n)
    steps = 0
    for _ in range(n):
        for _ in range(n):
            steps += 1
    return steps

def main() -> None:
    n = 8
    counts = {
        "constant": constant_steps(n),
        "logarithmic": logarithmic_steps(n),
        "linear": linear_steps(n),
        "linearithmic": linearithmic_steps(n),
        "quadratic": quadratic_steps(n),
    }
    assert counts == {
        "constant": 1,
        "logarithmic": 3,
        "linear": 8,
        "linearithmic": 24,
        "quadratic": 64,
    }

    print(f"n: {n}")
    print(f"O(1) model steps: {counts['constant']}")
    print(f"O(log n) model steps: {counts['logarithmic']}")
    print(f"O(n) model steps: {counts['linear']}")
    print(f"O(n log n) model steps: {counts['linearithmic']}")
    print(f"O(n²) model steps: {counts['quadratic']}")
    print("Growth check passed")

if __name__ == "__main__":
    main()

Run:

python3 growth_demo.py

Output:

n: 8
O(1) model steps: 1
O(log n) model steps: 3
O(n) model steps: 8
O(n log n) model steps: 24
O(n²) model steps: 64
Growth check passed

Observe the logarithmic model: 8 → 4 → 2 → 1, which reduces three times. If n is not a power of two, the exact number of iterations depends on the loop boundary; nonetheless, the complexity remains Θ(log n).

Recognizing Growth Patterns from Code

Constant: Workload Independent of Input Length

def first(values):
    if not values:
        return None
    return values[0]

Accessing array indices is treated as a constant-time operation here, so the time complexity is Θ(1). Whether the function first checks for an empty array does not change the growth rate.

Linear: Each Element Processed Once

def contains(values, target):
    for value in values:
        if value == target:
            return True
    return False

In the best case, if the target is at the first position, only Θ(1) checks are needed. In the worst case, where the target is not present, all n elements must be examined, resulting in Θ(n) checks. This illustrates that "big O" and "worst-case" are distinct dimensions.

Quadratic: Complete Double Loop Range

def all_ordered_pairs(values):
    pairs = []
    for left in values:
        for right in values:
            pairs.append((left, right))
    return pairs

The outer loop runs n times, and for each iteration, the inner loop executes n times, producing a total of n² pairs. Thus, both time and output space complexity are Θ(n²). A space analysis must explicitly account for the storage used by the returned results.

Three Common Misconceptions

"O(n) means exactly n steps are executed"

Not quite. O(n) denotes an upper bound category. 5n + 100, n/2, and n can all represent linear growth; if both upper and lower bounds are linear, it can be written as Θ(n).

"If data doubles, runtime must follow the growth table exactly"

Big-O complexity describes the long-term trend of computational work. Actual runtime is also influenced by caching, compiler optimizations, interpreter behavior, memory allocation, and input characteristics. Complexity analysis should be paired with real-world benchmarking.

"Any two nested loops means O(n²)"

You must also consider the scope of each loop. If the outer loop iterates over n elements and the inner loop traverses an array of length m, the time complexity is Θ(nm). If the two loops execute sequentially, their time complexities should be added. The next section will walk through this step-by-step with runnable code.

Your First Analysis

For each of the following three functions, write down: input size, basic operation, best-case scenario, and worst-case scenario.

def last(values):
    return values[-1]

def count_positive(values):
    count = 0
    for value in values:
        if value > 0:
            count += 1
    return count

def find_duplicate(values):
    for left in range(len(values)):
        for right in range(left + 1, len(values)):
            if values[left] == values[right]:
                return True
    return False

Reference conclusions:

• last is Θ(1) under constant-time indexing; an empty list raises IndexError, so returning the final item also requires nonempty input.
• count_positive scans all elements regardless of how many positive numbers there are, with time complexity of Θ(n) and auxiliary space of Θ(1).
• find_duplicate can return quickly when it finds the first pair of duplicates; if no duplicates exist, it checks n(n - 1)/2 pairs, with worst-case time complexity of Θ(n²) and auxiliary space of Θ(1).

Record the First Analysis in Three Lines

When facing a piece of code, first write down what n represents. Then choose a model operation, and finally describe how the number of operations grows as n increases. Complete these three lines for last, count_positive, and find_duplicate separately, and report both the best and worst-case scenarios.

Change n = 8 to 16 and verify that the linear, linear-logarithmic, and quadratic models produce 16, 64, and 256 respectively. This experiment validates the model steps, not the wall clock. Actual runtime is still influenced by the interpreter, caching, and input content.

Write down what n means and what operation you count each time. A different cost model may require a different conclusion for the same program.

Next Step: Turning Code Shape into an Expression

The next lesson will address sequential blocks, nested loops with dependent bounds, binary search processes, multiple inputs and output spaces, and the hidden costs of library operations.

Continue learning common complexity analysis