Introduction

Determining time and space complexity is mostly about identifying how often each part of the code runs as the input grows. The trick is not memorizing labels like O(n) or O(log n), but learning how loops, nesting, recursion, and data structures combine into a growth pattern.

Start With What Depends on Input Size

The first question is always: which variables grow with input size n?

Operations that do not depend on n are constant-time from an asymptotic point of view, even if they involve several ordinary statements.

For example:

1def f(a, b):
2    x = a + b
3    y = x * 2
4    return y - 1

This is O(1) time because the amount of work does not grow with the input size.

Analyze Loops by Counting Iterations

A single loop that runs n times is usually O(n) if the loop body is constant work.

1def sum_array(arr):
2    total = 0
3    for value in arr:
4        total += value
5    return total

If arr has length n, this is O(n) time.

Nested loops multiply when their iteration counts depend on the same input size.

1def all_pairs(arr):
2    for i in range(len(arr)):
3        for j in range(len(arr)):
4            print(arr[i], arr[j])

Here the outer loop runs n times and the inner loop also runs n times for each outer iteration, so the total is O(n^2).

Sequential Blocks Usually Add, Then Simplify

If code has one O(n) block followed by one O(n^2) block, the total is:

• 'O(n + n^2)'
• which simplifies to O(n^2)

The dominant growth term wins.

That is why asymptotic analysis usually drops constants and lower-order terms. They matter for raw performance tuning, but not for big-O classification.

Watch for Shrinking Inputs

Not every loop is linear. If the input size shrinks by a constant factor each step, the complexity is often logarithmic.

1def halve_until_zero(n):
2    steps = 0
3    while n > 0:
4        n //= 2
5        steps += 1
6    return steps

This is O(log n) because each iteration cuts n roughly in half.

The same logic appears in binary search, heap operations, and balanced tree traversals.

Recursion Follows the Same Logic

For recursive code, count:

• how much work happens per call
• how many recursive calls are made
• how fast the problem size shrinks

Example:

1def binary_search_like(n):
2    if n <= 1:
3        return 1
4    return binary_search_like(n // 2)

This is O(log n) because there is one recursive call per level and the input halves each time.

By contrast, a recursion that branches into two recursive calls on half-size subproblems often lands near O(n) or O(n log n) depending on the per-level work.

Space Complexity Matters Too

Time complexity is only half the story. Ask whether the code allocates additional memory that grows with n.

Examples:

• a few scalar variables: O(1) extra space
• a copied array of size n: O(n) extra space
• recursion depth of log n: O(log n) call-stack space

For instance:

1def copy_array(arr):
2    result = []
3    for value in arr:
4        result.append(value)
5    return result

This is O(n) extra space because result grows with the input.

A Good Step-by-Step Method

When you are given unfamiliar code, this sequence works well:

1. identify the input size variable
2. count loop or recursion depth
3. determine whether nested parts multiply or sequential parts add
4. identify the dominant term
5. repeat the process for memory usage

That keeps the analysis mechanical instead of guess-based.

Common Pitfalls

The biggest mistake is counting source lines instead of counting how often they execute. Complexity is about growth with input, not about visual code length.

Another mistake is treating every nested loop as O(n^2). If the inner loop depends on a different variable or a shrinking bound, the result may be different.

People also forget to analyze space separately. An algorithm can be fast in time and still expensive in memory.

Finally, avoid mixing worst-case, average-case, and best-case analysis without saying which one you mean. Big-O is usually used for upper bounds, but the context still matters.

Summary

• Complexity comes from how execution count grows with input size.
• Constant work repeated n times is usually O(n).
• Nested dependent loops often multiply; sequential blocks usually add, then simplify.
• Shrinking-by-half patterns often lead to O(log n).
• Analyze both time and extra space, not just runtime.