< _

Big O Notation Explained With Python Examples

Abstract generated cover for Big O Notation Explained With Python Examples.

Big O notation is a way to describe how an algorithm grows as the input gets bigger. It does not tell you exactly how many milliseconds code will take. It does not care about your laptop, your programming language, or whether one line of code is slightly faster than another line. Big O asks a bigger question:

What happens when the input grows? That question matters because code that feels instant for 10 items can become painful for 10 million items.

The Mental Model

Imagine you are checking whether a name exists in a list. If the list has 10 names, scanning through the list is fine. If the list has 10 million names, scanning through the entire list every time may be a problem. Big O helps you talk about that growth. Some common Big O categories:

| Big O | Name | Rough meaning |
| --- | --- | --- |
| O(1) | Constant time | Does not grow with input size |
| O(log n) | Logarithmic time | Grows slowly as input grows |
| O(n) | Linear time | Grows directly with input size |
| O(n log n) | Linearithmic time | Common for efficient sorting |
| O(n²) | Quadratic time | Gets expensive quickly |

The `n` represents the size of the input. If you have a list of 100 items, `n` is 100. If you have a list of 1,000,000 items, `n` is 1,000,000.

O(1): Constant Time

Constant time means the operation takes about the same number of steps no matter how large the input is.

users = ["maya", "alex", "tristan", "jordan"]

first_user = users[0]

Getting the first item by index is O(1). Python does not need to scan the whole list. It can go straight to that position. Another common example is dictionary lookup:

user_emails = {
    "maya": "[email protected]",
    "tristan": "[email protected]",
}

email = user_emails["tristan"]

Dictionary lookup is usually treated as O(1) on average. That is why dictionaries are so useful when you need fast key-based access.

O(n): Linear Time

Linear time means the work grows in direct proportion to the input.

def contains_user(users, target):
    for user in users:
        if user == target:
            return True
    return False

In the worst case, the target might be at the end of the list or not in the list at all. That means we may need to check every item. If the list has 10 users, we might check 10 items. If the list has 10,000 users, we might check 10,000 items. That is O(n). Linear time is not bad by default. It is often perfectly reasonable. But it becomes important when the input is large or the operation happens frequently.

O(n²): Quadratic Time

Quadratic time usually appears when you loop through the input inside another loop.

def print_pairs(items):
    for first in items:
        for second in items:
            print(first, second)

If there are 10 items, this prints 100 pairs. If there are 1,000 items, this prints 1,000,000 pairs. That grows fast. Nested loops are not always wrong, but they are a sign that you should pay attention.

O(log n): Logarithmic Time

Logarithmic time often appears when the algorithm cuts the problem down by a large chunk each step. Binary search is the classic example.

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left <= right:
        middle = (left + right) // 2
        guess = numbers[middle]

        if guess == target:
            return middle
        if guess < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

Binary search only works on sorted data. But when the data is sorted, it is very efficient because each step eliminates about half the remaining search space. For a million items, binary search does not need a million checks. It needs around 20. That is why O(log n) is powerful.

Common Mistakes

Mistake 1: Thinking Big O predicts exact speed

Big O describes growth, not exact runtime. An O(n) solution can be faster than an O(1) solution for small inputs if the O(1) solution has expensive setup. Big O becomes more useful as input size grows.

Mistake 2: Ignoring the input size

If you are building a small script that processes 20 rows, a simple loop is fine. If you are processing millions of records, the same loop might need more thought. Context matters.

Mistake 3: Treating every nested loop as a disaster

Nested loops often mean O(n²), but not always. Sometimes the inner loop runs a fixed number of times. Sometimes the total work is still closer to O(n). Look at the actual relationship between the input and the number of operations.

Where This Shows Up in Real Projects

Big O matters when:

  • a page slows down because it loops through too much data
  • a backend endpoint scans too many records
  • a script works on test data but fails on real data
  • a UI freezes while filtering or sorting
  • a database query needs an index You do not need to calculate Big O for every line of code. But when something might grow, Big O gives you a useful way to reason about it.

Key Takeaways

  • Big O describes how work grows as input size grows.
  • O(1) means constant time.
  • O(n) means work grows linearly with the input.
  • O(n²) can get expensive quickly.
  • O(log n) is common when the problem is repeatedly cut down.

  • Big O is about growth, not exact runtime.

    Related Articles

  • Time Complexity vs Space Complexity

  • Binary Search Explained With Examples
  • Arrays Explained: Indexing, Searching, and Updating

← Back to Blog Index