Time and Space Complexity

Analogy categoryAnalogies

Introduction

Time complexity and space complexity are the two primary metrics used to evaluate how efficient an algorithm is. Time complexity measures how the running time of an algorithm grows as the size of its input grows, while space complexity measures how much additional memory an algorithm requires as the input grows. These metrics abstract away the specifics of hardware and programming language so that algorithms can be compared fairly and predict how they will scale.

🏏

Cricket analogy: Time complexity is like how many overs a bowling attack takes to dismiss a growing batting lineup as the team size increases, while space complexity is like how many extra players the reserve bench needs; both let you compare strategies fairly regardless of stadium.

How It Works

Instead of measuring actual seconds or bytes (which vary by machine), we count the number of basic operations or memory units relative to input size, usually denoted n. Time complexity focuses on operations such as comparisons, additions, and assignments as n grows large. Space complexity focuses on the extra memory an algorithm allocates beyond the input itself, such as auxiliary arrays, recursion stack frames, or hash tables. Both are typically expressed using asymptotic notation (most commonly Big-O) which describes the growth rate rather than an exact count, focusing on behavior as n approaches infinity.

🏏

Cricket analogy: Instead of timing overs with a stopwatch on a specific ground, analysts count the number of deliveries relative to squad size n, and Big-O describes how that count grows as n gets huge, not the exact seconds on a given day.

Example

python

def sum_array(numbers):
    total = 0
    for num in numbers:       # loop runs n times -> O(n) time
        total += num
    return total               # O(1) extra space (just 'total')


def duplicate_array(numbers):
    copy = []
    for num in numbers:       # O(n) time
        copy.append(num)      # also allocates O(n) extra space
    return copy


def fibonacci_recursive(n):
    # Exponential time O(2^n) due to repeated recomputation
    # Space is O(n) due to the recursion call stack depth
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


numbers = [3, 7, 1, 9, 4]
print("Sum:", sum_array(numbers))
print("Copy:", duplicate_array(numbers))
print("Fibonacci(6):", fibonacci_recursive(6))

Analysis

sum_array touches every element exactly once, giving it O(n) time complexity, but it only ever stores a single running total, so its space complexity is O(1) — constant, regardless of input size. duplicate_array also runs in O(n) time, but because it builds a brand-new list the same size as the input, its space complexity is O(n) as well. fibonacci_recursive demonstrates a costly case: because each call spawns two more calls without caching results, the number of calls grows exponentially, giving O(2^n) time, even though the recursion depth (and therefore stack space) only grows linearly to O(n). This shows that time and space complexity can differ dramatically for the same algorithm and must be analyzed separately.

🏏

Cricket analogy: Totaling a team's runs by touching each of n scorecards once is O(n) time but needs only one running-total variable, O(1) space; duplicating the whole scoreboard into a new sheet is still O(n) time but now O(n) space; and recursively computing Fibonacci-style bonus points without memoization explodes to O(2^n) calls while the recursion stack itself only grows to O(n).

Key Takeaways

Time complexity measures how running time scales with input size n.
Space complexity measures how extra memory usage scales with input size n.
Both are usually expressed with asymptotic notation like Big-O.
An algorithm can be time-efficient but space-inefficient, or vice versa.
Recursive algorithms often trade time for stack space, or vice versa, depending on implementation.

Practice what you learned

1. What does time complexity measure?

2. In the sum_array example, why is the space complexity O(1)?

3. Why does fibonacci_recursive have O(2^n) time complexity?

4. Which statement about time and space complexity is TRUE?

Was this page helpful?

Introduction to Data Structures

Big-O Notation

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#TimeAndSpaceComplexity#Time#Space#Complexity#Works#Algorithms#StudyNotes#SkillVeris