DSA Notes

Time and Space Complexity — A Complete Beginner

Understand time complexity and space complexity from scratch. Learn what Big O notation means, how to read and calculate it, why it matters in real programs, and how to compare algorithms using O(1), O(log n), O(n), O(n²), and more — with detailed examples and visual explanations.

Introduction

Imagine you are given two different programs that both solve the same problem correctly. Which one is better? The obvious answer might be: "the one that runs faster." But how do you measure "faster" in a way that is meaningful and consistent across different computers, different languages, and different input sizes?

This is exactly the problem that complexity analysis solves. It gives us a mathematical language — Big O notation — to describe how an algorithm's resource consumption (time and memory) grows as the input gets larger.

Understanding complexity is not an optional academic exercise. It is a fundamental practical skill. A program that works correctly on 100 items but becomes unusably slow on 1 million items is not a good program. Complexity analysis tells you which of your solutions will scale and which will collapse under real-world conditions.

This lesson teaches you complexity analysis from the ground up — no prior mathematical background required.

What Is Big O Notation?

Big O notation is a mathematical notation that describes the upper bound on how an algorithm's running time (or space usage) grows as the input size n approaches infinity.

The formal definition: f(n) = O(g(n)) means there exist positive constants c and n₀ such that f(n) ≤ c × g(n) for all n ≥ n₀.

But practically speaking, Big O answers the question: "As n gets very large, which term in the operation count dominates everything else?"

The Two Key Rules

Rule 1 — Drop constants: If an algorithm takes exactly 5n operations, we write O(n), not O(5n). The constant 5 becomes irrelevant when n is enormous.

Rule 2 — Drop lower-order terms: If an algorithm takes n² + 3n + 7 operations, we write O(n²), not O(n² + 3n + 7). When n is very large (say, one million), n² is one trillion, 3n is three million, and 7 is negligible. Only the dominant term matters.

Exact count	4n³ + 2n² + 100n + 50
Big O	O(n³) ← only the highest-order term
Exact count	7 log n + 3
Big O	O(log n) ← only the dominant term
Exact count	15
Big O	O(1) ← constant, no n at all

The Common Complexity Classes

O(1) — Constant Time

An algorithm runs in O(1) time if it always performs the same number of operations regardless of input size.

Characteristics:

The best possible complexity
Performance does not change as input grows
No loops, no recursion based on input size

Examples:

Example

# Accessing an element by index in an array — always 1 operation def get_element(array, index): return array[index] # O(1) # Inserting at the end of a Python list — O(1) amortized def append_element(lst, element): lst.append(element) # O(1) # Checking if a key exists in a dictionary — O(1) average def has_key(dictionary, key): return key in dictionary # O(1) average # Getting the size of an array — O(1) (size is stored) def get_size(array): return len(array) # O(1)

Real-world example: Looking up a word in a hash-based dictionary. No matter how many words the dictionary contains (100 or 100 million), a hash lookup always takes approximately the same number of steps.

Performance at scale:

n (input size)	Operations
10	1
1,000	1
1,000,000	1
1,000,000,000	1

O(log n) — Logarithmic Time

An algorithm runs in O(log n) time if it reduces the problem size by a constant factor (typically in half) at each step.

Characteristics:

The second-best complexity after O(1)
Grows extremely slowly as n increases
Typically appears in divide-and-conquer algorithms and balanced tree operations

Why logarithmic? If you keep halving n until you reach 1, the number of halvings is log₂(n). For n = 1,000,000, that is only about 20 halvings.

Example — Binary Search:

Example

def binary_search(sorted_array, target): """ Search for target in a sorted array. At each step, we eliminate half the remaining elements. """ left = 0 right = len(sorted_array) - 1 while left <= right: middle = (left + right) // 2 if sorted_array[middle] == target: return middle # Found elif sorted_array[middle] < target: left = middle + 1 # Target is in the RIGHT half else: right = middle - 1 # Target is in the LEFT half return -1 # Not found # For an array of 1,000,000 elements: # Step 1: Check element 500,000 → remaining: 500,000 # Step 2: Check element 750,000 → remaining: 250,000 # Step 3: Check element 875,000 → remaining: 125,000 # ... # Step 20: Only 1 element remains → found or not found # Total: at most 20 steps for 1,000,000 elements

Performance at scale:

n (input size)	Operations (log₂ n)
10	~3
1,000	~10
1,000,000	~20
1,000,000,000	~30

This table illustrates the power of logarithmic algorithms. Doubling the input size adds only ONE more step.

O(n) — Linear Time

An algorithm runs in O(n) time if the number of operations grows proportionally with the input size.

Characteristics:

Very common and generally acceptable for most tasks
Appears when you must look at every element at least once
A single loop through all elements

Examples:

Example

def find_maximum(array): """Find the largest element — must check every element once.""" if len(array) == 0: return None maximum = array[0] for element in array: # n iterations — must check all if element > maximum: maximum = element return maximum # Time: O(n) — one pass through all n elements def calculate_sum(array): """Calculate sum of all elements.""" total = 0 for element in array: # n iterations total += element return total # Time: O(n) def linear_search(array, target): """Search without any special ordering.""" for i in range(len(array)): # Up to n iterations if array[i] == target: return i return -1 # Time: O(n) worst case

Note on multiple sequential loops: Two separate loops that each iterate through all n elements give O(n) + O(n) = O(2n) = O(n), not O(n²). Constants are dropped.

Example

def two_pass_algorithm(array): # Pass 1: Find maximum — O(n) maximum = max(array) # Pass 2: Normalize all elements — O(n) return [x / maximum for x in array] # Total: O(n) + O(n) = O(2n) = O(n)

Performance at scale:

n (input size)	Operations
10	10
1,000	1,000
1,000,000	1,000,000
1,000,000,000	1,000,000,000

O(n log n) — Log-Linear Time

An algorithm runs in O(n log n) time when it performs a logarithmic-time operation for each of the n elements.

Characteristics:

The optimal complexity for comparison-based sorting algorithms
Slower than O(n) but much faster than O(n²) for large inputs
Appears in Merge Sort, Heap Sort, and many divide-and-conquer algorithms

Example — Merge Sort:

Example

def merge_sort(array): """ Divide the array in half recursively, then merge sorted halves. Each level of recursion does O(n) work. There are O(log n) levels. Total: O(n log n) """ if len(array) <= 1: return array # Divide — O(1) to find midpoint mid = len(array) // 2 left_half = array[:mid] right_half = array[mid:] # Conquer — two recursive calls sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) # Combine — O(n) to merge two sorted halves return merge(sorted_left, sorted_right) def merge(left, right): """Merge two sorted arrays into one sorted array — O(n).""" result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result

Performance at scale:

n (input size)	O(n log n) operations
10	~33
1,000	~10,000
1,000,000	~20,000,000
1,000,000,000	~30,000,000,000

O(n²) — Quadratic Time

An algorithm runs in O(n²) time when it has nested loops, each iterating through all (or most) of the n elements.

Characteristics:

Acceptable for small inputs (n ≤ 1,000)
Becomes very slow for large inputs
Appears in simple sorting algorithms (Bubble Sort, Selection Sort, Insertion Sort) and naive pair-checking

Example — Bubble Sort:

Example

def bubble_sort(array): """ For each of n elements, compare it with each other element. Two nested loops, each running n times. """ n = len(array) for i in range(n): # Outer loop: n times for j in range(0, n - i - 1): # Inner loop: n-i-1 times if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] return array # Total comparisons: n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 = O(n²)

Example — Finding all pairs:

Example

def find_all_pairs(array): """Generate every possible pair from the array.""" pairs = [] n = len(array) for i in range(n): # n iterations for j in range(i + 1, n): # up to n iterations each pairs.append((array[i], array[j])) return pairs # Total pairs: n(n-1)/2 = O(n²)

Performance at scale (why O(n²) is dangerous):

n (input size)	O(n²) operations	Time at 10⁹ ops/sec
100	10,000	Instant
10,000	100,000,000	0.1 seconds
100,000	10,000,000,000	10 seconds
1,000,000	1,000,000,000,000	11.6 days

An O(n²) algorithm that is fast on your test data of 100 items will be catastrophically slow in production with 1 million items.

O(2ⁿ) — Exponential Time

An algorithm runs in O(2ⁿ) time when each step doubles the work, or when it explores all possible subsets or combinations.

Characteristics:

Completely impractical for n > 40-50
Appears in naive recursive solutions (like the naive Fibonacci algorithm)
Usually replaced with dynamic programming or other optimization

Example — Naive Fibonacci (wrong approach):

python example

def fibonacci_naive(n):
    """
    VERY SLOW — exponential time.
    Each call makes two more calls, forming a binary tree of calls.
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# For n=5, the recursion tree:
#                    fib(5)
#                  /        \
#             fib(4)        fib(3)
#           /       \      /     \
#        fib(3)  fib(2) fib(2)  fib(1)
#        /   \   / \    / \
#     fib(2)fib(1)...  ...  ...
#
# fib(3) is computed twice, fib(2) is computed three times!
# Total calls for fib(n) ≈ 2ⁿ

Performance at scale:

n	O(2ⁿ) operations
10	1,024
20	1,048,576
40	1,099,511,627,776 (~1 trillion)
50	~1 quadrillion
60	~1 quintillion

O(n!) — Factorial Time

The worst common complexity class. Appears when generating all permutations of n items.

For n = 20, n! ≈ 2.4 × 10¹⁸ — a number larger than the estimated number of atoms in the Earth. Even one operation per nanosecond would take 76 years.

Space Complexity

Everything above describes time complexity — how operation count grows. Space complexity describes how memory usage grows with input size, using the same Big O notation.

Counting Space

When calculating space complexity, we count:

Extra arrays, lists, or structures created by the algorithm
Recursive call stack depth (each function call uses stack space)
We do NOT count the input itself (just the auxiliary/extra space)

Examples of Space Complexity

O(1) space — Constant extra space:

Example

def find_max(array): # Uses only one extra variable (maximum) # Space: O(1) — same regardless of array size maximum = array[0] for element in array: if element > maximum: maximum = element return maximum

O(n) space — Linear extra space:

python example

def reverse_copy(array):
    # Creates a new array of the same size
    # Space: O(n)
    result = []
    for element in reversed(array):
        result.append(element)
    return result

O(n) space from recursion:

python example

def factorial(n):
    # Each recursive call adds a stack frame
    # Maximum stack depth: n frames
    # Space: O(n)
    if n <= 1:
        return 1
    return n * factorial(n - 1)

O(log n) space from recursion:

Example

def binary_search_recursive(array, target, left, right): # Recursive binary search: depth of recursion = log n # Space: O(log n) if left > right: return -1 mid = (left + right) // 2 if array[mid] == target: return mid elif array[mid] < target: return binary_search_recursive(array, target, mid + 1, right) else: return binary_search_recursive(array, target, left, mid - 1)

The Time-Space Trade-Off

In algorithm design, time and space often trade off against each other. Using more memory can often reduce execution time, and using less memory often requires more computation.

Classic example — Finding duplicates:

Example

# APPROACH 1: O(n²) time, O(1) space # Slow but memory-efficient def has_duplicate_slow(array): n = len(array) for i in range(n): for j in range(i + 1, n): # Compare every pair if array[i] == array[j]: return True return False # APPROACH 2: O(n log n) time, O(1) space # Sort first, then adjacent duplicates appear together def has_duplicate_medium(array): sorted_array = sorted(array) # O(n log n) time, O(n) space (sorted copy) for i in range(1, len(sorted_array)): if sorted_array[i] == sorted_array[i - 1]: return True return False # APPROACH 3: O(n) time, O(n) space # Fast but uses extra memory for the set def has_duplicate_fast(array): seen = set() # Extra memory: O(n) for element in array: # One pass: O(n) if element in seen: # O(1) lookup return True seen.add(element) # O(1) insert return False

All three approaches solve the same problem correctly. The right choice depends on your constraints:

If memory is severely limited → Approach 1 or 2
If speed is critical → Approach 3
In most practical situations → Approach 3 (modern hardware has plenty of RAM)

How to Calculate Big O — A Step-by-Step Method

Follow these steps for any algorithm:

Step 1: Identify the basic operation (the operation performed most frequently, usually an assignment, comparison, or arithmetic operation).

Step 2: Count how many times this operation runs as a function of n.

Step 3: Keep only the highest-order term.

Step 4: Drop all coefficients and constants.

Worked Example 1 — Simple Loop

python example

def count_positives(array):
    count = 0                   # 1 operation (constant)
    for x in array:             # n iterations
        if x > 0:               # 1 comparison per iteration
            count += 1          # at most 1 addition per iteration
    return count                # 1 operation (constant)

# Total operations: 1 + n × 2 + 1 ≈ 2n + 2
# Drop constants and coefficients: O(n)

Worked Example 2 — Nested Loop

python example

def print_multiplication_table(n):
    for i in range(1, n + 1):       # n iterations
        for j in range(1, n + 1):   # n iterations for each i
            print(i * j)            # 1 operation per pair

# Total operations: n × n × 1 = n²
# Big O: O(n²)

Worked Example 3 — Loop That Halves

python example

def count_halvings(n):
    count = 0
    i = n
    while i > 0:          # How many times can we halve n before reaching 0?
        i = i // 2        # n → n/2 → n/4 → n/8 → ... → 1 → 0
        count += 1
    return count

# After k iterations, i = n / 2^k
# Loop stops when n / 2^k < 1, i.e., when 2^k > n, i.e., k > log₂(n)
# Total iterations: ⌊log₂(n)⌋ + 1 ≈ log n
# Big O: O(log n)

Worked Example 4 — Recursive Function

python example

def sum_digits(n):
    """Sum the digits of a number recursively."""
    if n < 10:
        return n                     # Base case: 1 operation
    return (n % 10) + sum_digits(n // 10)    # Recursive case

# How many times does this recurse?
# n → n//10 → n//100 → ... → single digit
# Number of recursive calls = number of digits in n = log₁₀(n)
# Big O: O(log n)

Complexity Classes Compared Visually

Example

At n = 10: O(1) = 1 O(log n) = 3 O(n) = 10 O(n²) = 100 At n = 100: O(1) = 1 O(log n) = 7 O(n) = 100 O(n²) = 10,000 At n = 1,000: O(1) = 1 O(log n) = 10 O(n) = 1,000 O(n²) = 1,000,000 At n = 1,000,000: O(1) = 1 O(log n) = 20 O(n) = 1,000,000 O(n log n) = 20,000,000 O(n²) = 1,000,000,000,000 ← one trillion O(2ⁿ) = 10^301,030 ← incomprehensibly large

Summary

Time and space complexity analysis gives us a mathematical, machine-independent way to reason about algorithm efficiency.

Key points:

Big O notation describes the upper bound on growth rate, ignoring constants and lower-order terms.
O(1) — Constant: perfect, does not grow with n.
O(log n) — Logarithmic: excellent, grows very slowly.
O(n) — Linear: good, grows proportionally.
O(n log n) — Log-linear: the best achievable for comparison-based sorting.
O(n²) — Quadratic: acceptable for small n, dangerous for large n.
O(2ⁿ) — Exponential: impractical beyond n ≈ 40.
Space complexity measures additional memory usage with the same Big O notation.
Time-space trade-offs are fundamental: faster algorithms often use more memory.

In the next section, you will learn each of these concepts in much greater detail with formal proofs, recurrence relations, and advanced techniques.

*Next Section: Algorithm Analysis — A deep dive into Big O, Big Omega, Big Theta, recurrence relations, and the Master Theorem.*

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Time and Space Complexity — A Complete Beginner.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, introduction, time, and

Related Data Structures & Algorithms Topics

Continue learning this concept

IntroductionAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherUnderstand the precise difference between an algorithm and a data structure, how they relate to each other, why both are necessary, and how to choose the right combination to solve any programming problem efficiently.IntroductionApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareA comprehensive look at how data structures and algorithms are used in real systems — search engines, GPS navigation, social media, databases, operating systems, compilers, games, and more. With detailed explanations of which specific data structures and algorithms are used and why.IntroductionWhat is DSA? — A Complete BeginnerLearn what Data Structures and Algorithms (DSA) really means, why every programmer must know it, and how it forms the foundation of all software systems — with clear explanations and real-world examples.IntroductionWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueDiscover exactly why Data Structures and Algorithms matters for your programming career, how it affects your salary, how it powers real-world systems, and why mastering it is the single best investment a developer can make.Algorithm AnalysisSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsA complete guide to space complexity analysis — what counts as auxiliary space, how to analyze iterative and recursive algorithms, how recursion creates implicit stack space, common space complexity classes with examples, and the fundamental time-space tradeoffs every programmer must understand.Algorithm AnalysisTime Complexity Examples — 25 Worked Problems from Basic to AdvancedMaster time complexity analysis through 25 carefully chosen worked examples, from single loops to complex recursive algorithms. Each example provides step-by-step analysis, the final Big O answer, and key insights. An essential practice resource for interviews and deeper understanding.

PreviousApplications of DSA — How Data Structures and Algorithms Power Real-World Software NextWhat is DSA? — A Complete Beginner

DSA Notes

Time and Space Complexity — A Complete Beginner

Introduction

This lesson teaches you complexity analysis from the ground up — no prior mathematical background required.

What Is Big O Notation?

Big O notation is a mathematical notation that describes the upper bound on how an algorithm's running time (or space usage) grows as the input size n approaches infinity.

The formal definition: f(n) = O(g(n)) means there exist positive constants c and n₀ such that f(n) ≤ c × g(n) for all n ≥ n₀.

But practically speaking, Big O answers the question: "As n gets very large, which term in the operation count dominates everything else?"

The Two Key Rules

Rule 1 — Drop constants: If an algorithm takes exactly 5n operations, we write O(n), not O(5n). The constant 5 becomes irrelevant when n is enormous.

Exact count	4n³ + 2n² + 100n + 50
Big O	O(n³) ← only the highest-order term
Exact count	7 log n + 3
Big O	O(log n) ← only the dominant term
Exact count	15
Big O	O(1) ← constant, no n at all

The Common Complexity Classes

O(1) — Constant Time

An algorithm runs in O(1) time if it always performs the same number of operations regardless of input size.

Characteristics:

The best possible complexity
Performance does not change as input grows
No loops, no recursion based on input size

Examples:

Example

Performance at scale:

n (input size)	Operations
10	1
1,000	1
1,000,000	1
1,000,000,000	1

O(log n) — Logarithmic Time

An algorithm runs in O(log n) time if it reduces the problem size by a constant factor (typically in half) at each step.

Characteristics:

The second-best complexity after O(1)
Grows extremely slowly as n increases
Typically appears in divide-and-conquer algorithms and balanced tree operations

Why logarithmic? If you keep halving n until you reach 1, the number of halvings is log₂(n). For n = 1,000,000, that is only about 20 halvings.

Example — Binary Search:

Example

Performance at scale:

n (input size)	Operations (log₂ n)
10	~3
1,000	~10
1,000,000	~20
1,000,000,000	~30

This table illustrates the power of logarithmic algorithms. Doubling the input size adds only ONE more step.

O(n) — Linear Time

An algorithm runs in O(n) time if the number of operations grows proportionally with the input size.

Characteristics:

Very common and generally acceptable for most tasks
Appears when you must look at every element at least once
A single loop through all elements

Examples:

Example

Note on multiple sequential loops: Two separate loops that each iterate through all n elements give O(n) + O(n) = O(2n) = O(n), not O(n²). Constants are dropped.

Example

def two_pass_algorithm(array): # Pass 1: Find maximum — O(n) maximum = max(array) # Pass 2: Normalize all elements — O(n) return [x / maximum for x in array] # Total: O(n) + O(n) = O(2n) = O(n)

Performance at scale:

n (input size)	Operations
10	10
1,000	1,000
1,000,000	1,000,000
1,000,000,000	1,000,000,000

O(n log n) — Log-Linear Time

An algorithm runs in O(n log n) time when it performs a logarithmic-time operation for each of the n elements.

Characteristics:

The optimal complexity for comparison-based sorting algorithms
Slower than O(n) but much faster than O(n²) for large inputs
Appears in Merge Sort, Heap Sort, and many divide-and-conquer algorithms

Example — Merge Sort:

Example

Performance at scale:

n (input size)	O(n log n) operations
10	~33
1,000	~10,000
1,000,000	~20,000,000
1,000,000,000	~30,000,000,000

O(n²) — Quadratic Time

An algorithm runs in O(n²) time when it has nested loops, each iterating through all (or most) of the n elements.

Characteristics:

Acceptable for small inputs (n ≤ 1,000)
Becomes very slow for large inputs
Appears in simple sorting algorithms (Bubble Sort, Selection Sort, Insertion Sort) and naive pair-checking

Example — Bubble Sort:

Example

Example — Finding all pairs:

Example

Performance at scale (why O(n²) is dangerous):

n (input size)	O(n²) operations	Time at 10⁹ ops/sec
100	10,000	Instant
10,000	100,000,000	0.1 seconds
100,000	10,000,000,000	10 seconds
1,000,000	1,000,000,000,000	11.6 days

An O(n²) algorithm that is fast on your test data of 100 items will be catastrophically slow in production with 1 million items.

O(2ⁿ) — Exponential Time

An algorithm runs in O(2ⁿ) time when each step doubles the work, or when it explores all possible subsets or combinations.

Characteristics:

Completely impractical for n > 40-50
Appears in naive recursive solutions (like the naive Fibonacci algorithm)
Usually replaced with dynamic programming or other optimization

Example — Naive Fibonacci (wrong approach):

python example

def fibonacci_naive(n):
    """
    VERY SLOW — exponential time.
    Each call makes two more calls, forming a binary tree of calls.
    """
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

# For n=5, the recursion tree:
#                    fib(5)
#                  /        \
#             fib(4)        fib(3)
#           /       \      /     \
#        fib(3)  fib(2) fib(2)  fib(1)
#        /   \   / \    / \
#     fib(2)fib(1)...  ...  ...
#
# fib(3) is computed twice, fib(2) is computed three times!
# Total calls for fib(n) ≈ 2ⁿ

Performance at scale:

n	O(2ⁿ) operations
10	1,024
20	1,048,576
40	1,099,511,627,776 (~1 trillion)
50	~1 quadrillion
60	~1 quintillion

O(n!) — Factorial Time

The worst common complexity class. Appears when generating all permutations of n items.

For n = 20, n! ≈ 2.4 × 10¹⁸ — a number larger than the estimated number of atoms in the Earth. Even one operation per nanosecond would take 76 years.

Space Complexity

Everything above describes time complexity — how operation count grows. Space complexity describes how memory usage grows with input size, using the same Big O notation.

Counting Space

When calculating space complexity, we count:

Extra arrays, lists, or structures created by the algorithm
Recursive call stack depth (each function call uses stack space)
We do NOT count the input itself (just the auxiliary/extra space)

Examples of Space Complexity

O(1) space — Constant extra space:

Example

O(n) space — Linear extra space:

python example

def reverse_copy(array):
    # Creates a new array of the same size
    # Space: O(n)
    result = []
    for element in reversed(array):
        result.append(element)
    return result

O(n) space from recursion:

python example

def factorial(n):
    # Each recursive call adds a stack frame
    # Maximum stack depth: n frames
    # Space: O(n)
    if n <= 1:
        return 1
    return n * factorial(n - 1)

O(log n) space from recursion:

Example

The Time-Space Trade-Off

In algorithm design, time and space often trade off against each other. Using more memory can often reduce execution time, and using less memory often requires more computation.

Classic example — Finding duplicates:

Example

All three approaches solve the same problem correctly. The right choice depends on your constraints:

If memory is severely limited → Approach 1 or 2
If speed is critical → Approach 3
In most practical situations → Approach 3 (modern hardware has plenty of RAM)

How to Calculate Big O — A Step-by-Step Method

Follow these steps for any algorithm:

Step 1: Identify the basic operation (the operation performed most frequently, usually an assignment, comparison, or arithmetic operation).

Step 2: Count how many times this operation runs as a function of n.

Step 3: Keep only the highest-order term.

Step 4: Drop all coefficients and constants.

Worked Example 1 — Simple Loop

python example

def count_positives(array):
    count = 0                   # 1 operation (constant)
    for x in array:             # n iterations
        if x > 0:               # 1 comparison per iteration
            count += 1          # at most 1 addition per iteration
    return count                # 1 operation (constant)

# Total operations: 1 + n × 2 + 1 ≈ 2n + 2
# Drop constants and coefficients: O(n)

Worked Example 2 — Nested Loop

python example

def print_multiplication_table(n):
    for i in range(1, n + 1):       # n iterations
        for j in range(1, n + 1):   # n iterations for each i
            print(i * j)            # 1 operation per pair

# Total operations: n × n × 1 = n²
# Big O: O(n²)

Worked Example 3 — Loop That Halves

python example

def count_halvings(n):
    count = 0
    i = n
    while i > 0:          # How many times can we halve n before reaching 0?
        i = i // 2        # n → n/2 → n/4 → n/8 → ... → 1 → 0
        count += 1
    return count

# After k iterations, i = n / 2^k
# Loop stops when n / 2^k < 1, i.e., when 2^k > n, i.e., k > log₂(n)
# Total iterations: ⌊log₂(n)⌋ + 1 ≈ log n
# Big O: O(log n)

Worked Example 4 — Recursive Function

python example

def sum_digits(n):
    """Sum the digits of a number recursively."""
    if n < 10:
        return n                     # Base case: 1 operation
    return (n % 10) + sum_digits(n // 10)    # Recursive case

# How many times does this recurse?
# n → n//10 → n//100 → ... → single digit
# Number of recursive calls = number of digits in n = log₁₀(n)
# Big O: O(log n)

Complexity Classes Compared Visually

Example

Summary

Time and space complexity analysis gives us a mathematical, machine-independent way to reason about algorithm efficiency.

Key points:

Big O notation describes the upper bound on growth rate, ignoring constants and lower-order terms.
O(1) — Constant: perfect, does not grow with n.
O(log n) — Logarithmic: excellent, grows very slowly.
O(n) — Linear: good, grows proportionally.
O(n log n) — Log-linear: the best achievable for comparison-based sorting.
O(n²) — Quadratic: acceptable for small n, dangerous for large n.
O(2ⁿ) — Exponential: impractical beyond n ≈ 40.
Space complexity measures additional memory usage with the same Big O notation.
Time-space trade-offs are fundamental: faster algorithms often use more memory.

In the next section, you will learn each of these concepts in much greater detail with formal proofs, recurrence relations, and advanced techniques.

*Next Section: Algorithm Analysis — A deep dive into Big O, Big Omega, Big Theta, recurrence relations, and the Master Theorem.*

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Time and Space Complexity — A Complete Beginner.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, introduction, time, and

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousApplications of DSA — How Data Structures and Algorithms Power Real-World Software NextWhat is DSA? — A Complete Beginner