Length and iteration methods in Python - Time & Space Complexity

Time Complexity: Length and iteration methods

O(n)

Understanding Time Complexity

When we use length and iteration methods in Python, we want to know how the time to run the code changes as the input grows.

We ask: How many steps does the program take when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def sum_elements(lst):
    total = 0
    n = len(lst)
    for i in range(n):
        total += lst[i]
    return total

This code calculates the sum of all numbers in a list by first getting its length, then adding each element one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element of the list once.
• How many times: Exactly as many times as there are elements in the list (n times).

How Execution Grows With Input

As the list gets bigger, the number of steps grows in a straight line with the number of items.

Input Size (n)	Approx. Operations
10	About 10 additions
100	About 100 additions
1000	About 1000 additions

Pattern observation: Doubling the list size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly in proportion to the number of items in the list.

Common Mistake

[X] Wrong: "Calling len() inside the loop makes the code slower by a lot."

[OK] Correct: In Python, len() runs in constant time, so calling it once or many times does not change the overall time much compared to looping through the list.

Interview Connect

Understanding how length and iteration affect time helps you explain how your code scales, a key skill in many programming tasks.

Self-Check

"What if we replaced the for loop with a list comprehension that sums elements? How would the time complexity change?"