Python Understand O(1), O(log n), O(n), and O(n log n)

Learn the common complexity classes by tracking how much work a program repeats.

What You Will Learn

O(1) describes bounded work, O(log n) often comes from repeatedly halving a search space, O(n) from scanning every item, and O(n log n) from many comparison-based sorting algorithms. Complexity does not by itself specify wall-clock time or memory use. The assumptions about your data structure and operation matter.

Step-by-Step Example

The example below makes the behavior visible with small input values that you can change safely.

def halve_until_zero(value):
    steps = 0
    while value > 0:
        value //= 2
        steps += 1
    return steps

for amount in (8, 16, 32, 64):
    print(amount, halve_until_zero(amount))

How the Example Works

The function halve_until_zero defines reusable behavior; its body executes when it is called, not when it is declared.
The loop demonstrates when each value is processed or when cleanup and exception handling take effect.
The print() calls make the return values or state visible so you can compare them with the explanation and check your prediction.

Expected output from the example:

When You Would Use This

Decide which input types are valid, what output should be produced, and which cases should fail clearly. A small self-contained demonstration is a good starting point before adding file access, network calls, or application state.

Practice: Modify the Code

Replace the halving loop with value -= 1 and compare step growth.

Verify the changed output against the behavior described above, including the relevant invalid or boundary case.

For complete parameters and version details, consult the official Python documentation.

Common Beginner Mistakes

Assuming doubling input always doubles running time for every kind of algorithm.
Using worst-case O(1) claims for an operation whose average and worst behavior differ.

Key Takeaways

Learn the common complexity classes by tracking how much work a program repeats.
O(1) describes bounded work, O(log n) often comes from repeatedly halving a search space, O(n) from scanning every item, and O(n log n) from many comparison-based sorting algorithms.
Apply this operation only after checking the assumptions and input conditions shown in the example.