What is Big O? 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

Welcome to Big O Notation — the language we use to talk about how fast (or slow) an algorithm is! ⏱️

💡 Think of it like this: Imagine you have a phone book with 1,000 names. To find someone, you could read every name from the start (slow!) or open to the middle and keep halving (fast!). Big O tells us HOW the time grows as the input gets bigger.

# O(1) — Constant: Same time no matter what
def get_first(arr):
    return arr[0]  # Always 1 step

# O(n) — Linear: Time grows with input
def find(arr, target):
    for x in arr:  # n items = n steps
        if x == target:
            return True

# O(n²) — Quadratic: Time grows SQUARED
def all_pairs(arr):
    for i in arr:      # n times
        for j in arr:  # n times each = n × n total!
            print(i, j)

Big O from fastest to slowest:

⚡ O(1) — Constant: Array access, hash lookup
🏃 O(log n) — Logarithmic: Binary search (halving each step)
🚶 O(n) — Linear: Single loop through data
🐢 O(n log n) — Linearithmic: Good sorting (merge sort, quick sort)
🐌 O(n²) — Quadratic: Nested loops (bubble sort)
💀 O(2ⁿ) — Exponential: Brute force subsets

We only care about the dominant term as n gets very large. O(3n² + 5n + 100) simplifies to O(n²) because n² dominates when n is huge.

Why does this matter? If your algorithm is O(n²) and n = 1,000,000 — that's 1,000,000,000,000 operations. Your program could take HOURS. An O(n) algorithm does it in seconds! Choosing the right algorithm is everything. 🏆

📋 Instructions

Let's start simple! Write a function `describe_big_o()` that prints the following Big O complexities: ``` O(1) - Constant O(log n) - Logarithmic O(n) - Linear O(n log n) - Linearithmic O(n^2) - Quadratic O(2^n) - Exponential ``` Then call the function at the bottom.

Use print() for each line. For example: print('O(1) - Constant'). Make sure you print all 6 lines in order from fastest to slowest.

← Back to Course Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›