Week 10 — The real cost of list operations

The big question

Why can two loops with the same number of iterations have very different costs? Because the operation inside each iteration may become more expensive as the list grows. This week connects the counting methods you already know to ordinary list operations. You do not need to memorize Python internals. You need to recognize when work means a direct access, a search, a shift, or a copy.

By the end, explain why indexing is constant time, why front operations are linear, and why repeated front insertion becomes quadratic. Explain amortized append without claiming every append is equally fast. Rewrite a list-building method while preserving its output, and distinguish the memory used by the answer from additional working memory.

Türkçe: Döngünün kaç kez çalıştığını bilmek tek başına yeterli değildir. Her turda yapılan iş büyüyor mu? Bir kutuya doğrudan ulaşmak ile bütün kutuları bir yer kaydırmak aynı maliyette değildir. Bu hafta kodu ezberlemek yerine bu farkı görmeyi öğreniyoruz.

Prerequisite warm-up, with answers

For data = [10, 20, 30, 40], answer three questions before continuing. What are data[2], data[1:3], and the number of items inspected when searching for the missing value 99 from left to right?

Answers: Indexing begins at zero, so data[2] is 30. A slice includes its start and excludes its stop, so data[1:3] creates [20, 30]. The missing-value search checks all four items. Indexing chooses a known position; membership must discover whether a suitable position exists.

Now add 0 + 1 + 2 + 3. The answer is 6. Pair the ends: 0 + 3 = 3 and 1 + 2 = 3, giving 2 × 3 = 6. This small sum will explain a large performance problem.

Read the operation before counting the loop

A Python list stores an ordered sequence of references. A reference points to an object; moving a reference is different from copying the object's entire contents. The list knows where its slots begin and how many slots it uses.

If slot numbers start at zero, reaching slot i uses a location calculation. It does not visit slots 0 through i first. This is why data[i] has O(1) cost in the usual list model. By contrast, a search for a value may inspect every slot, so its worst case is O(n), where n is the current list length.

These models assume simple, fixed-size values and comparisons. Comparing two very long strings introduces another input size. An O(n) operation also does not necessarily inspect n elements on every call: a search can find its answer immediately.

Worked example 1 — Four front insertions

Start empty and insert 0, 1, 2, 3 at the front. Count only the old references that must shift, separately from writing the new item.

Total shifts are 0 + 1 + 2 + 3 = 6. There are also four writes for the new values. For n insertions, shifts are 0 + 1 + ... + (n − 1).

Write this sum forwards and backwards. Each paired column becomes n − 1, and there are n columns. Thus twice the sum is n(n − 1). Divide by two: shifts = n(n − 1)/2. Including the n new writes gives n(n − 1)/2 + n = (n² + n)/2, which is O(n²).

At n = 1,000, shifts are 1,000 × 999 / 2 = 499,500. At n = 2,000, they are 2,000 × 1,999 / 2 = 1,999,000. The ratio is about 4.002, approaching four rather than being exactly four.

Türkçe: Her turda n kaydırma yapılmıyor; ilk turda sıfır, sonra bir, iki, üç yapılıyor. Bu yüzden kesin sayı bir toplamdır. O(n²) dememizin nedeni toplamın büyümesini n² teriminin belirlemesidir. Dört kat ifadesi büyük girdiler için yaklaşık büyüme davranışını anlatır.

Preserve the output when improving the method. Appending produces ascending order here; front insertion produces descending order. This replacement does the same job:

data = []
for value in range(4):
    data.append(value)
data.reverse()
assert data == [3, 2, 1, 0]
print(data)

Appending n items costs O(n) total and reversing costs another O(n). Add the phases: O(n) + O(n) = O(n). Consecutive phases add; they do not multiply.

Worked example 2 — Copying the growing answer

Consider result = result + [value]. The plus operation builds a new list. With values 0 through 3, the new list lengths are 1, 2, 3, 4. Therefore 10 references are placed into newly built lists: 1 + 2 + 3 + 4 = 10.

For n values this becomes n(n + 1)/2. At n = 1,000 it is 500,500 reference placements, versus 1,000 ordinary append writes plus occasional resizing. Both methods create the same ordered result, but they do not perform the same amount of copying.

A full slice has the same danger when repeated. Copying an n-item list once takes O(n) time and O(n) space. Copying it n times costs O(n²) time. If each temporary copy replaces the previous one, peak extra space may still be O(n). If all copies are stored, extra space becomes O(n²). Total work and peak simultaneous storage answer different questions.

Türkçe: Bellek hesabında “şimdi aynı anda kaç öğe tutuluyor?” diye sorarız. Zaman hesabında ise işlem boyunca yapılan bütün kopyalamaları toplarız. Bir milyon kopyalama adımı, aynı anda bir milyon öğe saklandığı anlamına gelmez.

Slow concept — Amortized does not mean random average

Imagine a teaching model whose capacity doubles when full: 1, 2, 4, 8, 16. Capacity means available slots; length means occupied slots. Python's exact growth policy is implementation-specific, so this is an explanatory model, not its literal allocation schedule.

To append eight items, suppose resizing copies 1, then 2, then 4 old references. The total is 7 copies, plus 8 new writes: 15 units. The average over this sequence is 15/8 = 1.875 units per append, although the append that crosses capacity four performs more work than an ordinary append.

For n = 2ᵏ items, where k is a nonnegative integer, the copies are 1 + 2 + ... + n/2 = n − 1. Including n writes gives 2n − 1. Dividing by n gives 2 − 1/n, less than two. For other n, the geometric sum still gives a constant multiple of n total work. That is the reason for O(1) amortized per append.

Amortized analysis spreads the total cost across a sequence of operations. It does not assume random inputs or claim an individual operation cannot be slow. A resizing append may be O(n) in the worst case. Both statements can be true.

Türkçe: Amortize maliyet, pahalı işlemin ücretini çok sayıda ucuz işleme bölüştürmektir. “Ortalama kullanıcıda hızlıdır” demiyoruz. Belirli bir işlem dizisinin toplam maliyetini sınırlıyoruz. Tek bir eklemenin pahalı olması, bütün eklemelerin pahalı olduğu anlamına gelmez.

Three graduated practice problems

Problem 1 — Identify the hidden work

A list contains six items. How many old references shift when removing its front? How many references are copied by data[1:4] on the original list? What is the worst-case number of equality checks for a missing value?

Solution 1 — Separate three different actions

Removing the front leaves five items, all of which shift left: five shifts. The slice selects indices 1, 2, 3: three copied references, O(k) with k = 3. The missing-value search inspects all six: six equality checks, O(n). The slice does not include index 4. These counts concern the original six-item list separately, not three consecutive operations on a changing list.

Problem 2 — Empty a queue

Jobs ["A", "B", "C", "D"] must be processed in arrival order. Repeatedly removing index zero shifts how many references in total? Give a suitable alternative and its total cost.

Solution 2 — Keep the order and change the container

The shifts are 3 + 2 + 1 + 0 = 6. For n jobs, they total n(n − 1)/2, so removal work is O(n²). A deque supports end operations without shifting the entire remaining sequence.

from collections import deque

queue = deque(["A", "B", "C", "D"])
processed = []
while queue:
    processed.append(queue.popleft())
assert processed == ["A", "B", "C", "D"]
print(processed)

Construction is O(n); n left removals are O(n); collecting the answer is O(n). Total time remains O(n), with O(n) storage. A deque is suitable for this queue, but its middle indexing is not a constant-time replacement for list indexing.

Problem 3 — Diagnose a timing experiment

A benchmark starts with 100,000 items and calls pop() 200,000 times. It also reports that a single front removal doubles in time when n doubles. What must be corrected, and what can the timing support?

Solution 3 — Validate the experiment before its conclusion

The pop benchmark exhausts the list after 100,000 removals and raises IndexError on the next one. It cannot produce the claimed complete result. Use no more removals than available items, or benchmark an explicitly described balanced append/pop workload. Those are different experiments.

For single front removals, prepare a fresh list before each timed operation and keep construction outside that timing. A near-two ratio supports a linear shifting model. It does not prove a complexity bound. Timing an entire queue drain answers a different question and should approach a fourfold ratio instead.

Misconceptions to repair

“One Python statement is one unit of work” fails for slicing, searching, summing, and concatenation. Name the hidden operation. “Append is always O(1)” needs the amortized qualifier. “Faster code is equivalent code” fails when list order changes.

For text, collecting pieces and joining once avoids relying on repeated reconstruction. Measure total characters as well as piece count. Some interpreter contexts optimize repeated string concatenation, so a particular += timing need not show a quadratic curve. Do not manufacture a fourfold result. The general concatenation caution is documented in Python's sequence documentation.

Small English–Turkish glossary

Readiness, repair, and the next bridge

You are ready when you can derive the triangular sum, explain an expensive append without contradicting amortized O(1), and preserve a queue's order while improving its cost. If the sum feels mysterious, rebuild the four-row insertion table with six values. If space and time blur together, draw which copies are alive simultaneously. If timing feels decisive, state the operation count before looking at seconds.

Next week keeps the same question but changes the dominant operation: instead of shifting a list repeatedly, you will search it repeatedly. A set can help, provided its missing order and duplicate information do not change the answer.

One list instruction can move many items

A Python list stores references: links to its items. Removing the first item shifts the later references left to fill the gap. Removing the last item does not need these shifts. The items themselves do not have to be copied for this work to take time.

Draw or trace. Draw four slots A, B, C, D. Remove A, then show B, C and D moving one slot left. Repeat until empty and record the number of shifted references.

Predict before checking. How many total shifts occur when repeatedly removing from the front? Does one line of Python imply one unit of work?

Worked reasoning

The shift counts are 3, 2, 1, 0: six in total. With n starting items, the total is n(n − 1)/2, so repeatedly removing the first item gives quadratic work in this model. A short instruction can hide work that grows with the list. Append has amortised O(1) cost: the total work spread over many appends stays constant per append. One append can still be expensive.

values = list("ABCD")
shifts = 0
while values:
    shifts += len(values) - 1
    values.pop(0)
assert shifts == 6
print("Reference shifts:", shifts)

Change one thing. If the task allows reverse removal order, compare repeated end removal. If it requires removing items in their arrival order, changing removal order is not a valid optimisation.

Türkçe: Tek satır çok iş saklayabilir. Listenin başından silmek sonraki başvuruları kaydırır; daha hızlı işlem aynı çıktı sözleşmesini korumalıdır.

Additional analysis laboratory

This week is about hidden work inside familiar operations. Students should annotate one Python statement with the work it causes.

Extra exam-style prompt: A queue implementation repeatedly uses pop(0) on n jobs. Give the total shift count and a better container.

Solution: The shifts are n - 1, n - 2, ..., 0, totaling n(n - 1)/2. That is quadratic total shifting. A deque supports left removals efficiently for queue behavior, while preserving arrival order. It is not a drop-in replacement for every list use, especially random middle indexing.

Turkce: Tek satir kod tek is demek degildir. Listenin basindan silmek, kalan elemanlari kaydirir. Kuyruk davranisi istiyorsan veri yapisi secimi algoritmanin parcasidir.