Why lists are used in Python - Performance Analysis

Time Complexity: Why lists are used

O(n)

Understanding Time Complexity

We want to understand why lists are a popular choice in programming by looking at how their operations grow with input size.

What question are we trying to answer? How fast can we add, access, or search items in a list as it gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = []
for i in range(n):
    my_list.append(i)

value = my_list[5]

for item in my_list:
    if item == target:
        break

This code creates a list, adds items one by one, accesses an item by position, and searches for a target value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding items with append inside a loop.
• How many times: The append runs n times, once for each item.
• Access operation: Accessing an item by index happens once.
• Search operation: Looping through the list to find a target may run up to n times.

How Execution Grows With Input

As the list size grows, adding items takes longer because we do more appends.

Input Size (n)	Approx. Operations
10	About 10 appends, 1 access, up to 10 checks for search
100	About 100 appends, 1 access, up to 100 checks for search
1000	About 1000 appends, 1 access, up to 1000 checks for search

Pattern observation: Adding and searching grow roughly in direct proportion to the list size, while accessing by index stays quick.

Final Time Complexity

Time Complexity: O(n)

This means the time to add or search items grows linearly as the list gets bigger, but accessing by position stays very fast.

Common Mistake

[X] Wrong: "Accessing any item in a list takes longer as the list grows."

[OK] Correct: Access by index in a list is very fast and does not slow down with size because lists store items in contiguous memory and can jump directly to the position.

Interview Connect

Understanding how list operations grow helps you explain why lists are useful and when to choose them in real projects or interviews.

Self-Check

"What if we changed the list to a linked list? How would the time complexity for access and search change?"