When you search for a contact in your phone, it happens instantly. But what if your phone had to check every single contact one by one? With 1,000 contacts, that would take forever! This difference in speed is what time complexity measures.

Time complexity tells us how the runtime of an algorithm grows as the input size increases.

Why Time Complexity Matters

Imagine two algorithms that both find a number in a list:

Algorithm A: Checks every number one by one
Algorithm B: Uses a smart approach to check half the list each time

For a list of 1,000 numbers:

›Algorithm A: Might take 1,000 steps
›Algorithm B: Takes only 10 steps

Algorithm B is 100x faster! Time complexity helps us measure and compare this difference.

Key Idea: Time complexity measures how an algorithm's speed changes when we increase the input size, not the exact time in seconds.

What is Big-O Notation?

Big-O notation is the language we use to describe time complexity. It answers the question: "How does runtime grow as input size grows?"

Format: O(expression)

Examples:

›O(1) - Constant time
›O(n) - Linear time
›O(n²) - Quadratic time
›O(log n) - Logarithmic time

The "n" represents the input size (like the length of an array).

Understanding O(1) - Constant Time

Definition: Runtime stays the same no matter how big the input is.

Real-World Example: Accessing a book by page number. Whether the book has 100 pages or 10,000 pages, flipping to page 42 takes the same time.

Code Example

Python

# Accessing array element - O(1)
numbers = [10, 20, 30, 40, 50]

# Direct access - always takes same time
first = numbers[0]      # O(1)
last = numbers[4]       # O(1)

print(first)  # 10
print(last)   # 50

Analysis:

›Array size: 5, 100, or 1,000,000
›Access time: Always 1 step
›Time Complexity: O(1)

O(1) means: No matter how large the input, the algorithm takes the same number of steps.

Understanding O(n) - Linear Time

Definition: Runtime grows directly with input size. If input doubles, runtime doubles.

Real-World Example: Reading a book page by page. If the book has 100 pages, it takes 100 units of time. If it has 200 pages, it takes 200 units.

Code Example

Python

# Print all elements - O(n)
numbers = [10, 20, 30, 40, 50]

# Must visit each element once
for num in numbers:
    print(num)

# If array has 5 elements: 5 steps
# If array has 100 elements: 100 steps
# Time Complexity: O(n)

Analysis:

›Array size: n
›Steps: n (visit each element once)
›Time Complexity: O(n)

Understanding O(n²) - Quadratic Time

Definition: Runtime grows with the square of input size. If input doubles, runtime quadruples.

Real-World Example: Comparing every person with every other person in a room. With 10 people, that's 10 × 10 = 100 comparisons. With 20 people, it's 20 × 20 = 400 comparisons.

Code Example

Python

# Nested loops - O(n²)
numbers = [1, 2, 3, 4, 5]

# Outer loop runs n times
for i in numbers:
    # Inner loop runs n times for each outer iteration
    for j in numbers:
        print(f"({i}, {j})")

# Total iterations: n × n = n²
# Time Complexity: O(n²)

Analysis:

›Array size: n = 5
›Outer loop: 5 iterations
›Inner loop: 5 iterations per outer loop
›Total: 5 × 5 = 25 steps
›Time Complexity: O(n²)

Understanding O(log n) - Logarithmic Time

Definition: Runtime grows slowly as input increases. Doubling input adds only one more step.

Real-World Example: Finding a name in a phone book by opening to the middle, checking if you need to go left or right, then repeating. Each step eliminates half the remaining pages.

Code Example: Binary Search

Python

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

# Example
numbers = [10, 20, 30, 40, 50, 60, 70, 80]
result = binary_search(numbers, 40)
print(f"Found at index: {result}")  # 3

Analysis:

›Array size: 8 elements
›Step 1: Check middle (index 4) → not found
›Step 2: Check middle of left half (index 2) → not found
›Step 3: Check middle of new range (index 3) → found!
›Total steps: 3 = log₂(8)
›Time Complexity: O(log n)

Common Time Complexities Compared

Notation	Name	Example	n=10	n=100	n=1000
O(1)	Constant	Array access	1	1	1
O(log n)	Logarithmic	Binary search	3	7	10
O(n)	Linear	Loop through array	10	100	1000
O(n log n)	Linearithmic	Merge sort	30	700	10,000
O(n²)	Quadratic	Nested loops	100	10,000	1,000,000
O(2ⁿ)	Exponential	Recursive Fibonacci	1024	10³⁰	Very large

Key Insight: As input grows, O(1) and O(log n) scale well, while O(n²) and O(2ⁿ) become impractical.

How to Calculate Time Complexity

Rule 1: Drop Constants

Python

# Example 1
def example1(arr):
    print(arr[0])     # O(1)
    print(arr[0])     # O(1)
    print(arr[0])     # O(1)

# Total: O(1) + O(1) + O(1) = O(3)
# Simplified: O(1)  ← Drop the constant 3

Why? Constants don't affect growth rate as input size increases.

Rule 2: Drop Non-Dominant Terms

Python

# Example 2
def example2(arr):
    # First loop
    for num in arr:
        print(num)     # O(n)
    
    # Nested loops
    for i in arr:
        for j in arr:
            print(i, j)  # O(n²)

# Total: O(n) + O(n²)
# Simplified: O(n²)  ← Drop O(n), keep dominant term

Why? For large n, n² grows much faster than n.

Rule 3: Different Inputs = Different Variables

Python

# Example 3
def example3(arr1, arr2):
    for num in arr1:
        print(num)     # O(a) where a = len(arr1)
    
    for num in arr2:
        print(num)     # O(b) where b = len(arr2)

# Total: O(a + b)  ← NOT O(n) because different arrays

Practice Problems

Problem 1: Find Time Complexity

Python

def mystery_function(arr):
    n = len(arr)
    
    for i in range(n):
        print(arr[i])
    
    for i in range(n):
        for j in range(n):
            print(arr[i] + arr[j])

# What is the time complexity?
# Answer: O(n²)
# Explanation: O(n) + O(n²) = O(n²)

Problem 2: Compare Algorithms

Which is faster for n = 1000?

Algorithm A: O(n²)
Algorithm B: O(n log n)

Answer: Algorithm B

Calculation:

›Algorithm A: 1000² = 1,000,000 steps
›Algorithm B: 1000 × log(1000) ≈ 1000 × 10 = 10,000 steps

Algorithm B is 100x faster!

Real-World Impact

Example: Sorting Algorithms

Algorithm	Time Complexity	Time for 1,000 items
Bubble Sort	O(n²)	1,000,000 steps
Merge Sort	O(n log n)	10,000 steps
Quick Sort (average)	O(n log n)	10,000 steps

Impact: For large datasets, choosing the right algorithm makes the difference between instant results and waiting hours.

Best, Average, and Worst Case

Some algorithms perform differently based on input:

Linear Search Example

Python

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Best case: O(1) - target is first element
# Average case: O(n/2) → O(n) - target in middle
# Worst case: O(n) - target is last or not present

Note: We usually talk about worst-case complexity unless specified otherwise.

Key Takeaways

Big-O Notation describes how algorithm runtime grows with input size.

Common Complexities: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Rules: Drop constants, drop non-dominant terms, use different variables for different inputs.

Focus on worst case unless otherwise specified.

Choose algorithms wisely: For large inputs, O(n log n) is far better than O(n²).

What's Next?

Now that you understand time complexity:

›Space Complexity - Learn about memory usage
›Asymptotic Notation - Dive deeper into Big-O, Big-Θ, Big-Ω
›Array Basics - Apply time complexity to real data structures

Practice Exercises

Determine the time complexity of these code snippets:

Exercise 1

Python

def exercise1(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                print(i, j, k)

# Answer: O(n³) - three nested loops

Exercise 2

Python

def exercise2(arr):
    if len(arr) == 0:
        return
    print(arr[0])
    print(arr[len(arr) - 1])

# Answer: O(1) - constant operations

Ready to continue? Let's explore Space Complexity next!

←

PreviousWhat is an Algorithm?

NextSpace Complexity

→