Time and Space Complexity Analysis

From data shape to solution scale

In Introduction to Data Structures, you learned that data can be shaped differently depending on the job: trades, positions, lists, lookups, and relationships.

Now we need the next interview skill:

If the input gets much bigger, does your solution still work well?

This is what time and space complexity analysis answers.

For interview prep, especially at finance or quant-style firms, correctness is only step one. You also need to explain the cost of your choices clearly and confidently.

Big O describes growth

Big O notation is a way to describe how an algorithm's cost grows as input size grows.

If n is the number of items in the input:

• O(1) means constant growth
• O(n) means linear growth
• O(n²) means quadratic growth

Big O does not usually care about exact seconds. It cares about the shape of growth.

Example intuition

If a function checks every trade once, doubling the number of trades roughly doubles the work.

That is usually O(n).

A single pass is usually O(n)

When you see a loop over an input list, ask:

How many times does this loop run as the input grows?

If the list has n items and the loop touches each item once, the time complexity is usually O(n).

This is one of the most common patterns you will use in early interview problems.

```python
prices = [101, 98, 105, 110, 97]

count_above_100 = 0
steps = 0

for price in prices:
    steps += 1
    if price > 100:
        count_above_100 += 1

print("prices:", prices)
print("count above 100:", count_above_100)
print("loop steps:", steps)
print("time complexity: O(n)")
```

A function compares every item in a list with every other item using two nested loops over the same list of size n.

What is the most likely time complexity?

Big O focuses on dominant growth

Big O usually ignores:

• constant factors
• small fixed work
• lower-order terms

Why? Because for large inputs, the fastest-growing part dominates.

So this:

3n + 20 steps

is still described as:

O(n)

And this:

n² + n + 50 steps

is described as:

O(n²)

```python
def example_work(n):
    steps = 0

    # 20 fixed steps
    for _ in range(20):
        steps += 1

    # 3 passes over n items
    for _ in range(n):
        steps += 1
    for _ in range(n):
        steps += 1
    for _ in range(n):
        steps += 1

    return steps

for n in [10, 100, 1000]:
    print("n =", n, "steps =", example_work(n))

print("Even though this is 3n + 20, we describe it as O(n).")
```

True or false?

If a function creates a new list with one new item for every item in the input list, its extra space usage is O(n).

Complexity ladder

Here is a practical ranking you should start recognizing:

O(1)        constant
O(log n)    logarithmic
O(n)        linear
O(n log n)  common efficient sorting range
O(n²)       quadratic
O(2ⁿ)       exponential

For now, focus on recognizing the big early patterns:

• one direct access → often O(1)
• one loop → often O(n)
• nested loops → often O(n²)
• repeatedly cutting the search space → often O(log n)

We will use these patterns again when we reach arrays, searching, trees, and graphs.

Fill in the blank.

A function loops once over a list of n prices and does constant work for each price.

The time complexity is ____.

Time and space are different questions

When analyzing a solution, ask two separate questions:

1. Time: How many operations grow with input size?
2. Space: How much extra memory grows with input size?

A solution can be fast but use extra memory, or slower but use less memory.

In interviews, this tradeoff matters. Do not just say, “It is efficient.” Say what kind of efficiency you mean.

```python
def total_without_copy(values):
    total = 0
    for value in values:
        total += value
    return total


def copy_then_total(values):
    copied = []
    for value in values:
        copied.append(value)

    total = 0
    for value in copied:
        total += value
    return total

nums = [5, 10, 15]

print("total_without_copy:", total_without_copy(nums))
print("copy_then_total:", copy_then_total(nums))
print("Both are O(n) time.")
print("total_without_copy uses O(1) extra space.")
print("copy_then_total uses O(n) extra space.")
```

A simple way to explain complexity

When an interviewer asks for complexity, use this structure:

Let n be the size of the input.
The algorithm does ______ work because ______.
So the time complexity is O(______).
It uses ______ extra space because ______.
So the space complexity is O(______).

Example

Let n be the number of prices.
The algorithm scans the list once, doing constant work per price.
So the time complexity is O(n).
It only stores a few variables.
So the extra space complexity is O(1).

This lesson gives you the language you will use throughout the rest of the section. Next, in Arrays and Strings, you will apply this analysis to the most common interview input types.