Understanding Program Runtime Efficiency: Time and Space Complexity in Python

Program runtime efficiency consists of two aspects: time efficiency (time complexity) and space efficiency (space complexity). Time complexity measures how fast a program runs, while space complexity measures the additional memory required during execution.

Because exact execution time depends on hardware, we use asymptotic analysis with Big O notation to estimate performance. For example, an algorithm that runs a constant number of steps has O(1) complexity, while one that scales linearly with input size has O(n) complexity.

Space complexity quantifies the amount of temporary storage an algorithm needs, typically expressed as the number of variables or data structures used, also using Big O notation.

Python’s built‑in composite data types—tuple, list, set, and dictionary—have different operation costs. Detailed time‑complexity tables are available on the official Python wiki.

Data Lookup Efficiency

To compare lookup speed between a list and a set, the following script generates random numbers and measures how long it takes to search each structure:

<code>import time
import random
nums = [random.randint(0, 2000000) for i in range(1000)]
list_test = list(range(1000000))
set_test = set(list_test)
count_list, count_set = 0, 0
t1 = time.time()  # list lookup
for num in nums:
    if num in list_test:
        count_list += 1
t2 = time.time()
for num in nums:  # set lookup
    if num in set_test:
        count_set += 1
t3 = time.time()
print('Found counts, list: {}, set: {}'.format(count_list, count_set))
print('Time used, list: {:.4f}s'.format(t2 - t1))
print('Time used, set: {:.4f}s'.format(t3 - t2))
</code>

The output shows that the set lookup completes in about 0.001 s, while the list lookup takes roughly 7.8 s, clearly demonstrating the superior search efficiency of sets, especially with large data volumes.

Data Storage Overhead

Sets achieve faster lookups by storing additional metadata, which increases memory usage. Using sys.getsizeof() we can compare the memory footprints:

<code>import sys
import random
list_test = list(range(1000000))
set_test = set(range(1000000))
print('List size:', sys.getsizeof(list_test))
print('Set size:', sys.getsizeof(set_test))
</code>

The result indicates that the set occupies about 33.5 MB, whereas the list uses only about 9 MB, confirming that sets trade memory for speed.

In summary, choosing the appropriate data structure depends on the specific application: for small datasets the performance difference may be negligible, but for large datasets the choice between list and set has a significant impact on both speed and memory consumption.