Time Complexity

Difficulty: Advanced

Time complexity describes how the running time of an algorithm grows as the input size increases. It is expressed using Big O notation, which characterizes the upper bound of an algorithm's growth rate, focusing on the dominant term and ignoring constants and lower-order terms.

The most common time complexities, from fastest to slowest, are: O(1) constant time -- the operation takes the same time regardless of input size (e.g., accessing a list element by index, dictionary lookup). O(log n) logarithmic -- the problem size is halved each step (e.g., binary search). O(n) linear -- the time grows proportionally with input (e.g., iterating through a list). O(n log n) linearithmic -- common in efficient sorting algorithms (e.g., merge sort, Timsort). O(n^2) quadratic -- nested loops over the input (e.g., bubble sort). O(2^n) exponential -- recursive solutions that branch twice at each step (e.g., naive Fibonacci). O(n!) factorial -- generating all permutations.

Analyzing time complexity involves examining the structure of your code: single loops typically give O(n), nested loops give O(n^2) or O(n*m), and halving loops give O(log n). When combining operations, the total complexity is dominated by the most expensive one: O(n) + O(n^2) simplifies to O(n^2). When operations are nested, their complexities multiply: an O(n) loop containing an O(n) operation gives O(n^2).

Space complexity measures how much additional memory an algorithm uses relative to input size. An in-place algorithm uses O(1) extra space (e.g., bubble sort), while creating a copy of the input uses O(n) space. Recursive algorithms use O(depth) stack space. Space complexity is especially important when dealing with large datasets or memory-constrained environments.

In interviews, you will be expected to analyze the time and space complexity of your solutions and discuss trade-offs. A common pattern is trading space for time: using a hash set for O(1) lookups instead of scanning a list in O(n), or memoizing recursive results to avoid recomputation.

Code examples

Common time complexities demonstrated

# O(1) - Constant
def get_first(lst):
    return lst[0] if lst else None

# O(n) - Linear
def find_max(lst):
    maximum = lst[0]
    for num in lst:
        if num > maximum:
            maximum = num
    return maximum

# O(n^2) - Quadratic
def has_duplicates(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

print(get_first([10, 20, 30]))
print(find_max([3, 7, 2, 9, 4]))
print(has_duplicates([1, 2, 3, 2]))

get_first is O(1) because it accesses one element. find_max is O(n) because it checks every element once. has_duplicates is O(n^2) because the nested loop compares every pair.

O(log n) - Halving the search space

def count_halvings(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

print(f"n=8: {count_halvings(8)} steps")
print(f"n=1024: {count_halvings(1024)} steps")
print(f"n=1000000: {count_halvings(1000000)} steps")

Halving n each step results in log2(n) iterations. This is why binary search on 1 million elements takes at most ~20 comparisons, making O(log n) extremely efficient.

Time vs space trade-off: Two Sum problem

# O(n^2) time, O(1) space - brute force
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# O(n) time, O(n) space - hash map
def two_sum_hash(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

print(two_sum_brute([2, 7, 11, 15], 9))
print(two_sum_hash([2, 7, 11, 15], 9))

The brute force checks every pair (O(n^2) time, O(1) space). The hash map version uses extra memory to store seen values (O(n) space) but finds the answer in one pass (O(n) time). This is a classic time-space trade-off.

Analyzing nested loops with different bounds

def example_nested(n):
    count = 0
    for i in range(n):           # O(n)
        for j in range(n):       # O(n) -> total O(n^2)
            count += 1
    print(f"n={n}, n^2 ops: {count}")

    count2 = 0
    for i in range(n):           # O(n)
        for j in range(i):       # 0+1+2+...+(n-1) = n(n-1)/2
            count2 += 1
    print(f"n={n}, triangular ops: {count2}")

example_nested(5)
example_nested(10)

Both nested loops are O(n^2). The second loop runs 0+1+2+...+(n-1) = n(n-1)/2 times, which is still O(n^2) because we drop constants and lower-order terms in Big O analysis.

Key points

Concepts covered

Big O notation, space complexity, algorithm analysis