Why `s += "a"` Is O(N²) in Python

2026-01-04

Repeated string concatenation copies the whole string each time, making it O(N²); building a list and joining once is O(N).

Question

Consider the following Python code:

s = ""
for _ in range(N):
    s += "a"

What is the time complexity, and why does it behave that way?

Answer: Why This Becomes O(N²)

The key point is that Python strings are immutable.

When you write:

s += "a"

Python does not modify the existing string in place. Instead, it effectively performs:

s = s + "a"

Each iteration involves:

  1. Allocating a new string with length len(s) + 1
  2. Copying all characters from the old string s
  3. Copying the new character "a"

Accumulated cost

On the ith iteration, the length of s is i - 1, so the number of characters copied is proportional to i - 1.

The total number of copied characters is:

0 + 1 + 2 + 3 + ... + (N - 1)
= N(N - 1) / 2

This results in O(N²) time complexity.

Although only one character is appended each time, the repeated full-copy operations accumulate quadratically.

A Note on Implementation Details

Some Python implementations (including CPython) apply internal optimizations in certain cases, such as when a string has a single reference.

However:

  • These optimizations are implementation-dependent
  • They are not guaranteed by the language specification
  • They should not be relied upon for reasoning about algorithmic complexity

The Python documentation explicitly warns about this pattern.

From the official documentation:

“Concatenating immutable sequences always results in a new object. This means that building up a sequence by repeated concatenation will have a quadratic runtime cost in the total sequence length.”

Source: https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range

Optimization: Build First, Join Once

The idiomatic approach in Python is to accumulate strings in a list and join them once at the end:

parts = []
for _ in range(N):
    parts.append("a")

s = "".join(parts)

Why this is O(N)

str.join() works by:

  1. Computing the total length of the final string in advance
  2. Allocating memory only once
  3. Copying each character exactly once into the final buffer

As a result, the total amount of copying is proportional to the final string length, giving O(N) time complexity.

Summary

  • Python strings are immutable
  • Repeated concatenation causes repeated full copies
  • The difference between O(N) and O(N²) can come from a single line of code
  • Understanding how strings are implemented helps avoid hidden performance pitfalls