List length and membership test in Python - Time & Space Complexity

Time Complexity: List length and membership test

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check a list's length and find an item grows as the list gets bigger.

How does the program's work change when the list size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = [1, 2, 3, 4, 5]
length = len(my_list)
if 3 in my_list:
    print("Found 3")
else:
    print("3 not found")

This code gets the length of a list and checks if the number 3 is inside it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking if 3 is in the list (membership test).
• How many times: It may check each item once until it finds 3 or reaches the end.

How Execution Grows With Input

As the list gets bigger, finding the length stays quick, but checking for 3 takes longer if 3 is near the end or not there.

Input Size (n)	Approx. Operations
10	Length: 1 operation, Membership: up to 10 checks
100	Length: 1 operation, Membership: up to 100 checks
1000	Length: 1 operation, Membership: up to 1000 checks

Pattern observation: Length check is always fast and constant; membership test grows linearly with list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to check if an item is in the list grows in direct proportion to the list size.

Common Mistake

[X] Wrong: "Getting the length of a list takes time proportional to the list size."

[OK] Correct: The length is stored and accessed instantly, so it takes the same short time no matter how big the list is.

Interview Connect

Understanding how list operations scale helps you write efficient code and answer questions about performance clearly and confidently.

Self-Check

"What if we changed the list to a set? How would the time complexity of the membership test change?"