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?"

Practice

1.

What does the len() function do when used with a list in Python?

easy

A. It removes the last item from the list.

B. It checks if an item is in the list.

C. It adds a new item to the list.

D. It returns the number of items in the list.

Solution

1. Step 1: Understand the purpose of len()

   The len() function counts how many elements are inside a list.

2. Step 2: Compare with other options

   Checking membership uses in, adding uses append(), removing uses pop().

3. Final Answer:

   It returns the number of items in the list. -> Option D

4. Quick Check:

   len() counts items [OK]

Hint: Remember: len() counts items, in checks presence [OK]

Common Mistakes:

• Confusing len() with in operator
• Thinking len() adds or removes items
• Mixing up list methods with functions

2.

Which of the following is the correct syntax to check if the number 5 is in the list nums?

nums = [1, 3, 5, 7]

easy

A. if 5 inside nums:

B. if nums in 5:

C. if 5 in nums:

D. if nums contains 5:

Solution

1. Step 1: Recall correct membership syntax

   Python uses in to check if an item is inside a list: item in list.

2. Step 2: Check each option

   Only if 5 in nums: matches correct syntax; others are invalid Python.

3. Final Answer:

   if 5 in nums: -> Option C

4. Quick Check:

   Use in for membership test [OK]

Hint: Use 'item in list' to check membership [OK]

Common Mistakes:

• Writing 'inside' or 'contains' instead of 'in'
• Reversing order like 'list in item'
• Using invalid keywords for membership

3.

What will be the output of this code?

fruits = ['apple', 'banana', 'cherry']
print(len(fruits))
print('banana' in fruits)
print('orange' in fruits)

medium

A. 3\nTrue\nFalse

B. 3\nFalse\nTrue

C. Error\nTrue\nFalse

D. 3\nTrue\nTrue

Solution

1. Step 1: Calculate length of the list

   The list has 3 items: 'apple', 'banana', 'cherry', so len(fruits) is 3.

2. Step 2: Check membership for 'banana' and 'orange'

   'banana' is in the list, so 'banana' in fruits is True. 'orange' is not, so 'orange' in fruits is False.

3. Final Answer:

   3 True False -> Option A

4. Quick Check:

   len=3, banana in list=True, orange in list=False [OK]

Hint: Count items with len(), check presence with in [OK]

Common Mistakes:

• Confusing True/False for membership
• Miscounting list length
• Expecting syntax error for correct code

4.

Find the error in this code snippet:

items = [10, 20, 30]
if 20 in items
    print("Found 20")

medium

A. Missing colon ':' after the if condition.

B. Wrong use of 'in' operator.

C. List should be defined with parentheses, not brackets.

D. print statement syntax is incorrect.

Solution

1. Step 1: Check syntax of if statement

   Python requires a colon ':' at the end of the if condition line.

2. Step 2: Identify the missing colon

   The code has if 20 in items without a colon, causing a syntax error.

3. Final Answer:

   Missing colon ':' after the if condition. -> Option A

4. Quick Check:

   if statements need ':' [OK]

Hint: Always put ':' after if condition [OK]

Common Mistakes:

• Forgetting colon after if condition
• Misusing 'in' operator syntax
• Using parentheses instead of brackets for lists

5.

You have a list numbers = [2, 4, 6, 8]. You want to check if the list has exactly 4 items and if the number 5 is not in the list. Which code correctly does this?

hard

A. if len(numbers) = 4 and 5 not in numbers:
print("Condition met")

B. if len(numbers) == 4 and 5 not in numbers:
print("Condition met")

C. if len(numbers) == 4 or 5 in numbers:
print("Condition met")

D. if len(numbers) == 4 and 5 in numbers:
print("Condition met")

Solution

1. Step 1: Check list length condition

   Use len(numbers) == 4 to test if list has exactly 4 items.

2. Step 2: Check membership condition

   Use 5 not in numbers to confirm 5 is not in the list.

3. Step 3: Combine conditions correctly

   Use and to require both conditions true together.

4. Final Answer:

   if len(numbers) == 4 and 5 not in numbers: print("Condition met") -> Option B

5. Quick Check:

   Length check and membership negation combined with and [OK]

Hint: Use 'len() == number' and 'item not in list' with and [OK]

Common Mistakes:

• Using single '=' instead of '==' for comparison
• Using or instead of and for both conditions
• Checking for 5 in list instead of not in