🎓 A1Learner
🔍

DSA Time and Space

Time and space are the two costs of a program, counted in steps and in extra memory cells. An in-place method reuses the cells of its input and builds no second list.

Doubling into a new list

A cell is one slot that holds one value. This version builds a second list, so it holds one extra cell per value.

values = [1, 2, 3, 4]
new_list = []
for value in values:
    new_list.append(value * 2)
print(new_list)
print("Extra cells:", len(new_list))

Doubling in place

This version rewrites each cell inside the same list and builds nothing new. The doubled values match the first version, and the extra cells stay at zero.

values = [1, 2, 3, 4]
for i in range(len(values)):
    values[i] = values[i] * 2
print(values)
print("Extra cells:", 0)

One helper variable is cheap

A helper variable holds exactly one extra cell, however long the list grows. A fixed count like that is O(1) space.

values = [5, 9, 2]
largest = values[0]
for value in values:
    if value > largest:
        largest = value
print(largest)

Example

def double_new(values):
    result = []
    for value in values:
        result.append(value * 2)
    return result, len(result)

def double_in_place(values):
    for i in range(len(values)):
        values[i] = values[i] * 2
    return values, 0

original = [3, 6, 9, 12, 15]
copy = list(original)
print(double_new(original))
print(double_in_place(copy))

Key points

  • Every solution pays two costs, one in steps and one in extra memory
  • Time complexity: the step count of a program, stated in Big O
  • Space complexity: the extra cell count of a program, stated in Big O
  • In place: work that reuses the cells of the input and builds no second list
  • O(1) space: extra memory that stays fixed as the input grows

In this example, two functions double the same five numbers. The first function builds a fresh list and reports five extra cells. The second function rewrites the cells of a copy of the list and reports zero extra cells. Both print the same doubled list, so the answers match. Only the space cost differs, and the printed counts prove it.

Note

The input itself does not count as extra space, because the program was handed it.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A method doubles every value inside the list it was handed and builds no new list. What is its extra space?