Common Complexities 15 XP Easy

Ctrl+Enter Run Ctrl+S Save

Let's explore every common Big O complexity with real code examples. Understanding these by heart is essential.

O(1) — Constant Time
The operation takes the same time regardless of input size.

def get_first(arr):    # O(1)
    return arr[0]

def is_even(n):        # O(1)
    return n % 2 == 0

O(log n) — Logarithmic
The input is halved each step. Binary search is the classic example.

def binary_search(arr, target):  # O(log n)
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

O(n) — Linear
We visit each element once.

def find_sum(arr):    # O(n)
    total = 0
    for x in arr:
        total += x
    return total

O(n²) — Quadratic
Nested loops. Common in brute-force solutions.

def print_pairs(arr):  # O(n²)
    for i in arr:
        for j in arr:
            print(i, j)

Speed ranking from fastest to slowest:

O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2^n) → O(n!)

📋 Instructions

Write a function `complexity_of(description)` that takes a description string and returns the Big O notation. Handle these cases: - `"single operation"` → `"O(1)"` - `"loop through array"` → `"O(n)"` - `"nested loops"` → `"O(n^2)"` - `"binary search"` → `"O(log n)"` - `"sorting"` → `"O(n log n)"` Print the result for each test case.

Use if/elif to check the description string. For example: if description == 'single operation': return 'O(1)'. Handle each of the 5 cases.

🧪 Test Cases

Input

complexity_of("single operation")

Expected

O(1)

Test case 1

Input

complexity_of("loop through array")

Expected

O(n)

Test case 2

Input

complexity_of("nested loops")

Expected

O(n^2)

Test case 3

Input

complexity_of("binary search")

Expected

O(log n)

Test case 4

Input

complexity_of("sorting")

Expected

O(n log n)

Test case 5

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›