Python list append time complexity: why it's amortized O(1)

Python's list.append is fast because a list is a dynamic array: one block of memory with spare slots. Most appends fill a spare slot. When the block is full, CPython moves the list to a block about an eighth bigger, plus a few slots, which can mean copying every reference. These copies get rarer, so append is amortized O(1).

In this post we follow a weather station that logs one reading a minute, 525,600 readings a year, all added with append. We try the simple plan first and count its copies: 138 billion. Then we read how Python really grows a list, in its own source code, and measure it with sys.getsizeof. Last, we meet the slow end of a list, the front, and the fix for it.

A few words first. Memory is where a running program keeps its data. A block of memory is one piece of it, all in one place. A slot is one space in a block for one item. CPython is the standard Python that most people install, and the one we measure here. A dynamic array is a row of slots that can change size. O(1) means the number of steps stays the same, however big the list is; O(n) means about one step per item. If Big O is new to you, the Big O notation post explains it by counting steps.

This post goes with letsBug Code, episode 6. Watch it first, or read on: everything in the video is here, plus programs you can run to measure your own lists and practice questions with answers.

What happens when a Python list is full?

Start with real data. The United States runs automated weather stations called ASOS (Automated Surface Observing Systems). NCEI, the US weather agency's climate archive (National Centers for Environmental Information), says: "There are currently more than 900 ASOS sites in the United States." It also says: "NCEI also collects ASOS observations taken at finer timescales; 1-minute and 5-minute observations". In plain words: it keeps readings taken every minute.

One reading a minute makes a lot of readings: 60 minutes × 24 hours × 365 days = 525,600 readings a year. In Python you'd collect them one at a time, with readings.append(r).

Here's the problem. A Python list keeps its items in one block of memory, side by side. When the block is full, there's no room for the next item. So Python has to get a bigger block and copy every item across. If each new block were just one slot bigger, every append would copy the whole list, and a year of readings could take up to 138,127,417,200 copies. Yet append is fast.

How are Python lists stored in memory?

Python's own FAQ answers this: "CPython's lists are really variable-length arrays, not Lisp-style linked lists." Lisp is an old programming language. A linked list keeps each item with a link to the next one, so it can't jump straight to a position. An array is a row of slots side by side in memory. "Variable-length" means the row can change size. The FAQ goes on: "The implementation uses a contiguous array of references to other objects". The implementation is the way it's built. Contiguous means touching, with no gaps.

A reference is where an object lives in memory, like a note with an address on it. So a slot doesn't hold the reading itself. It holds a note saying where the reading is. Every note is the same size, so Python can work out where slot number 400,000 is with one quick calculation, and jump straight there. The FAQ says this "makes indexing a list a[i] an operation whose cost is independent of the size of the list or the value of the index." In plain words: getting an item takes the same time however long the list is, and whichever position you ask for. Indexing means getting an item by its position, like readings[400000]. It takes one step: O(1).

The problem is that a block has a fixed size, and the memory just after it may already be in use. The FAQ says: "When items are appended or inserted, the array of references is resized." Resizing a block of memory works in one of two ways. cppreference, a guide to the C programming language (the language CPython is written in), describes them for C's resize function, realloc. If possible, the old block grows where it is, when the memory after it is free. If not, it means "allocating a new memory block", copying the old contents into it, and then "freeing the old block." In plain words: grow the block in place if there's room; if not, get a new block, copy everything, and give the old one back.

We can't see from Python which way each resize went. So in this post, every copy count is a worst case: the most copies there could be, if every resize moves the whole list.

Why is growing an array one slot at a time O(n²)?

Try the simplest plan first. When the block is full, get a block one slot bigger and copy everything over. Trace eight appends into an empty list:

• The 1st append copies nothing: the list was empty.
• The 2nd copies 1 item, the 3rd copies 2, the 4th copies 3…
• The 8th copies 7.

That's 0 + 1 + 2 + … + 7 = 28 copies for 8 items. Each copy moves one reference into the new block. For n appends it's 0 + 1 + … + (n − 1) = n(n − 1)/2, the same sum as program A in the Big O post. So growing by one is O(n²): double the list, and the copying becomes four times as much.

You don't have to trust the sum. This program counts the copies for any plan that adds a fixed number of slots when the block is full:

def copies(n, grow):
    """Copies for n appends, if a full block grows by `grow` slots."""
    slots = total = 0
    for size in range(n):       # size = items already in the list
        if size == slots:       # full: copy them all to a bigger block
            total += size
            slots += grow
    return total

year = 60 * 24 * 365            # one reading a minute
print(copies(8, 1))
print(f"{copies(year, 1):,}")   # :, puts commas in big numbers
print(f"{copies(year, 10):,}")

28
138,127,417,200
13,812,505,200

Growing by one slot, a year of readings costs 138,127,417,200 copies: 525,600 × 525,599 / 2. The last line tries a bigger fixed step, 10 slots at a time. We'll come back to it.

How much does a Python list grow when it's full?

About one eighth, plus a few slots. Python doesn't grow a list by one slot. It over-allocates: it asks for more slots than it needs right now, so the next few appends have room. The FAQ says: "when the array must be grown, some extra space is allocated so the next few times don't require an actual resize."

The exact rule is in CPython's source code, in the file Objects/listobject.c, in a function called list_resize. Its comment says: "This over-allocates proportional to the list size, making room for additional growth." Proportional means the extra room grows as the list grows. The comment then lists the sizes a list goes through as you append: "The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ..."

The next line is the rule itself, in C:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Ignore the (size_t) parts: they only tell C what kind of number to use. Now read it in plain words. newsize is how many items the list needs to hold now. newsize >> 3 means newsize divided by 8, rounded down (computers store numbers in base 2, as bits: 0s and 1s. Moving them 3 places to the right halves the number 3 times, and 2 × 2 × 2 = 8). Add 6. Then & ~3 rounds the total down to a multiple of 4. The comment says why: "Add padding to make the allocated size multiple of 4." Padding here means extra slots. So the new block has room for the items, plus about an eighth more, plus a few.

Here is the same rule in Python. It starts with an empty list and resizes every time the list is full:

def new_slots(newsize):
    """CPython's rule: newsize + newsize/8 + 6, rounded down to a multiple of 4."""
    return (newsize + (newsize >> 3) + 6) & ~3

slots, pattern = 0, [0]
for size in range(1, 80):       # size = items after this append
    if size > slots:            # full: resize
        slots = new_slots(size)
        pattern.append(slots)
print(pattern)

[0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92]

That's the pattern from the comment, plus the next size, 92. Now let's check that a real list does the same. We can't see the slots directly, but we can see how much memory the list takes. sys.getsizeof does that. The Python docs say it will "Return the size of an object in bytes", and that it counts only the list itself, "not the memory consumption of objects it refers to." A byte is a small unit of memory. On our computer, an empty list takes 56 bytes, and each slot adds 8 more. So the number of slots is (the list's size − an empty list's size) ÷ 8:

import sys
readings = []
for r in range(17):
    readings.append(r)
    slots = (sys.getsizeof(readings) - sys.getsizeof([])) // 8
    print(len(readings), slots)

1 4
2 4
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
11 16
12 16
13 16
14 16
15 16
16 16
17 24

Each line shows the number of items, then the number of slots. Change range(17) to range(80) and you'll see the rest of the pattern: 32, 40, 52, 64, 76 and 92 slots. The first append makes a block of 4 slots. Appends 2, 3 and 4 just fill spare slots. The 5th append finds the block full, and the list moves to 8 slots. Then 16, then 24: the same pattern as the source code. We ran this in Python 3.13.2, 64-bit, on Windows. (64-bit means a memory address is 64 bits, which is 8 bytes: that's why each slot adds 8.) The growth rule is the same today in CPython's newest code (its main branch), where new versions are made. Other versions, or other Pythons like PyPy (a different program that also runs Python code), may grow differently.

Why is list append O(1) amortized?

Because the big copies are rare, and they get rarer as the list grows. Count again with the real plan. Eight appends: the list goes from 0 to 4 slots (nothing to copy), then from 4 to 8 slots (4 copies). That's 4 copies, not 28.

Now a whole year. This program appends 525,600 readings. Each time the slot count changes, it adds one resize, and counts the items that were in the list before as copies:

import sys
readings, slots, resizes, copies = [], 0, 0, 0
for r in range(525_600):
    before = len(readings)
    readings.append(r)
    now = (sys.getsizeof(readings) - sys.getsizeof([])) // 8
    if now != slots:
        resizes += 1
        copies += before
        slots = now
print(resizes, copies, slots)

81 4684900 586032

(525_600 is 525,600: the _ is just for reading.) Only 81 resizes in a year, and at most 4,684,900 copies. That's 4,684,900 ÷ 525,600 = at most 8.9 copies per append on average. Make the list longer and the average never reaches 9. It goes up to just under 9 right after a resize, then drops toward 8 as the spare slots fill. (We checked every length up to 5 million with the growth rule.)

So over many appends, each append costs O(1) steps once you share out the copying. It's true for every long run of appends, not just this one. That's called amortized O(1). To amortize a cost is to spread it out over time, like paying for a bike in small weekly amounts. Python's docs mark append's O(1) with a note: "Amortized. An individual operation may occasionally be O(n) when the underlying storage is resized, but this cost is spread over many operations". The underlying storage is the block of slots.

The big copies are real. In our year, the biggest single resize happened when the list held 520,912 readings. That one append copied up to 520,912 references, into a block of 586,032 slots. But after it, the list had 65,119 free slots: room for the next 65,119 appends without a single copy. The CPython comment calls this "linear-time amortized behavior over a long sequence of appends()": the steps for n appends grow in proportion to n. Here, it's under 9 copies per append.

Why do dynamic arrays grow by a fraction, not a fixed amount?

Because a fixed step still copies the whole list every few appends, so the total stays O(n²). Look back at the copy counter: growing by a fixed 10 slots still cost 13,812,505,200 copies for a year. It resizes every 10 appends, and every resize copies the whole list: 10 + 20 + 30 + … That's about n²/20, still O(n²). That's a tenth of the copies of growing by one, but far more than Python's plan.

When the block is full, grow by…	Copies for 525,600 appends	Big O
1 slot	138,127,417,200	O(n²)
10 slots	13,812,505,200	O(n²)
about 1/8 (CPython, measured)	4,684,900 at most	amortized O(1) each

Growing by an eighth works because a bigger list gets a bigger gap. After a resize, the list has about n/8 free slots, so the next n/8 appends are cheap. Each resize copies n items and buys about n/8 cheap appends: about 8 copies for each of them. Right after a resize, those cheap appends haven't happened yet, so the average is close to 9. As they happen, it drops back toward 8. That's why the average stays between 8 and 9. Growing by one makes nearly 30,000 times as many copies as Python's plan.

The price is memory. After a year of readings, the list has 586,032 slots for 525,600 readings: 60,432 slots are empty, about 10%. Python trades some unused memory for speed. The source calls this extra room "mild": "The over-allocation is mild".

Why are insert(0) and pop(0) slow in Python?

Because the front of a list has no spare room. To insert at the front, Python moves every item one slot to the right to make a gap. To pop from the front, it moves them all back. The Python docs put it like this: "inserting at index k shifts the elements from k onwards one slot to the right, moving n - k elements." And: "The worst case is index 0, where the whole rest of the list has to be moved". So insert(0, x) and pop(0) are O(n). Do them in a loop, and you're back to O(n²).

The end of a list is the fast end. The docs say "operating at the end of the list moves nothing and is O(1)." The Python tutorial sums it up: "While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one)."

If you need to add or remove at both ends, use a deque, from the collections module. The name is said "deck", and it's short for "double-ended queue". The docs say deques support "appends and pops from either side of the deque with approximately the same O(1) performance in either direction." Lists, they say, "incur O(n) memory movement costs for pop(0) and insert(0, v) operations". That is, they pay to move memory.

Steps aren't seconds, so let's time it. This builds a list of 50,000 readings three ways: append at the end, insert at the front, and appendleft on a deque, which adds at the front:

import time
from collections import deque

n = 50_000

start = time.perf_counter()
end_list = []
for r in range(n):
    end_list.append(r)          # add at the end
print(f"append:        {time.perf_counter() - start:.3f} s")

start = time.perf_counter()
front_list = []
for r in range(n):
    front_list.insert(0, r)     # add at the front
print(f"insert(0, r):  {time.perf_counter() - start:.3f} s")

start = time.perf_counter()
front_deque = deque()
for r in range(n):
    front_deque.appendleft(r)   # add at the front of a deque
print(f"appendleft(r): {time.perf_counter() - start:.3f} s")

On our laptop it printed:

append:        0.012 s
insert(0, r):  1.726 s
appendleft(r): 0.008 s

time.perf_counter() reads a clock, so the end time minus the start time is how long the loop took. Your times will be different, but insert(0, r) should still be far slower than the other two. On our laptop, inserting at the front took over 100 times as long as appending, even for this small list. The deque adds at the front about as fast as the list adds at the end.

Questions people ask

Is list append O(1) in Python?

Yes, amortized: shared out over many appends, it's O(1), and that is a promise for every long run of appends, not just a typical one. Most appends drop the item into a spare slot, which is one step. Once in a while the list is full and one append copies every item into a bigger block, which is O(n). Because the list grows by about an eighth each time, those copies average out to under 9 per append in our measurement.

What is a dynamic array?

An array that can change size. It keeps its items side by side in one block of memory, so it can jump to any position in one step. When the block is full, it moves to a bigger block. A Python list is a dynamic array of references.

What does amortized O(1) mean?

That an operation takes O(1) steps when you add up the cost of any long run of calls and share it out, even though a few single calls take longer. It's a promise for every run of calls, not just a likely one. For append, the rare slow call is a resize. To amortize means to spread a cost out, like paying for something in small amounts.

Is a Python list a linked list?

No. Python's FAQ says: "CPython's lists are really variable-length arrays, not Lisp-style linked lists." A linked list stores each item with a link to the next one, so finding item 400,000 means following the links one by one from the start. A Python list finds it in one step.

Why does sys.getsizeof not change after every append?

Because the list has spare slots. sys.getsizeof counts the slots the list has, used or not. It only changes when the list moves to a bigger block. It also doesn't count the items themselves, only the references to them.

Does a Python list shrink when you remove items?

Sometimes. In Python 3.13's source, a list gives memory back when its items drop below half of its slots. We measured it: 100 appends give 108 slots; popping from the end down to 53 items shrinks it to 64 slots.

When should I use a deque instead of a list?

When you add or remove items at the front, for example a queue where the first item in is the first item out. A deque is fast at both ends. A list is fast at the end and when you get items by position, like readings[400000].

Keep going

• Watch the full lesson, How Does append Work in Python? Dynamic Arrays and Amortized O(1), and its Short, Python Secretly Copies Your List. So Why Is append Fast? More in the letsBug Code series on YouTube. Next in the series: Python variables are name tags.
• The episode before this one: Big O notation in Python, and why 3 lines can be slower than 30.
• Another O(n²) sum, with every comparison counted: bubble sort and insertion sort in Python.
• Why one-step indexing matters: binary search in JavaScript and Python jumps to the middle of a list again and again.

Checked on 3 November 2026 against the 9 sources below.

Sources

• Python documentation: Design and History FAQ: How are lists implemented in CPython? (variable-length arrays of references, one-step indexing, extra space when the list grows)
• CPython source code: Objects/listobject.c, list_resize, 3.13 branch (the growth pattern, the growth rule, "linear-time amortized behavior", shrinking below half)
• CPython source code, main branch: Objects/listobject.c (the same growth comment and rule, today)
• Python documentation: Time complexity of operations on built-in types (append is amortized O(1), insert and pop at index k are O(n − k), the worst case is index 0)
• Python documentation: collections.deque (fast at both ends; lists pay O(n) for pop(0) and insert(0, v))
• Python tutorial: Using Lists as Queues (the front of a list is slow, the end is fast)
• Python documentation: sys.getsizeof (size in bytes, not counting the objects a list refers to)
• cppreference: realloc (a resize grows the block in place if possible, or copies to a new block)
• NOAA NCEI: Automated Surface/Weather Observing Systems (more than 900 ASOS sites in the US, 1-minute observations)

Every code sample in this post was run in Python 3.13.2 (64-bit, on Windows) before publishing, and every slot count and copy count was measured by running it.