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

Practice

1. Why do we use lists in Python?

easy

A. To store multiple items in one variable

B. To store only one item at a time

C. To perform mathematical calculations only

D. To create functions

Solution

1. Step 1: Understand the purpose of lists

   Lists are designed to hold many items together in one place.

2. Step 2: Compare options with list features

   Only To store multiple items in one variable correctly states that lists store multiple items in one variable.

3. Final Answer:

   To store multiple items in one variable -> Option A

4. Quick Check:

   Lists hold many items = To store multiple items in one variable [OK]

Hint: Lists hold many items together in one variable [OK]

Common Mistakes:

• Thinking lists store only one item
• Confusing lists with functions
• Assuming lists are for math only

2. Which of the following is the correct way to create a list in Python?

easy

A. my_list = [1, 2, 3]

B. my_list = (1, 2, 3)

C. my_list = {1, 2, 3}

D. my_list = <1, 2, 3>

Solution

1. Step 1: Recall list syntax in Python

   Lists are created using square brackets [] around items.

2. Step 2: Match options with correct syntax

   my_list = [1, 2, 3] uses square brackets, so it is correct. Others use parentheses, curly braces, or angle brackets which are incorrect for lists.

3. Final Answer:

   my_list = [1, 2, 3] -> Option A

4. Quick Check:

   Lists use [] brackets = my_list = [1, 2, 3] [OK]

Hint: Lists use square brackets [] to hold items [OK]

Common Mistakes:

• Using parentheses () which create tuples
• Using curly braces {} which create sets or dicts
• Using angle brackets <> which are invalid

3. What will be the output of this code?

fruits = ['apple', 'banana', 'cherry']
print(fruits[1])

medium

A. apple

B. IndexError

C. cherry

D. banana

Solution

1. Step 1: Understand list indexing

   Python lists start indexing at 0, so fruits[1] is the second item.

2. Step 2: Identify the item at index 1

   The list is ['apple', 'banana', 'cherry'], so index 1 is 'banana'.

3. Final Answer:

   banana -> Option D

4. Quick Check:

   fruits[1] = banana [OK]

Hint: List indexes start at 0, so index 1 is second item [OK]

Common Mistakes:

• Thinking index starts at 1
• Confusing list with dictionary
• Expecting an error for valid index

4. Find the error in this code that tries to add an item to a list:

my_list = [1, 2, 3]
my_list.add(4)
print(my_list)

medium

A. Missing brackets in print statement

B. Using add() instead of append() to add item

C. List cannot hold numbers

D. List must be declared with curly braces

Solution

1. Step 1: Identify method to add items to list

   Python lists use append() to add items, not add().

2. Step 2: Check the code for method usage

   The code uses my_list.add(4), which causes an error because add() is not a list method.

3. Final Answer:

   Using add() instead of append() to add item -> Option B

4. Quick Check:

   Use append() to add items to list [OK]

Hint: Use append() to add items to lists, not add() [OK]

Common Mistakes:

• Using add() which is for sets
• Thinking lists can't hold numbers
• Incorrect print syntax assumptions

5. You have a list of student names and want to add a new student, remove one who left, and keep the order. Which data structure should you use and why?

hard

A. Use a dictionary because it stores key-value pairs

B. Use a set because it automatically sorts items

C. Use a list because it keeps order and allows adding/removing items

D. Use a tuple because it is immutable

Solution

1. Step 1: Understand requirements for data structure

   The data structure must keep order and allow adding/removing students.

2. Step 2: Match requirements with data structure features

   Lists keep order and allow adding/removing items. Sets do not keep order. Dictionaries store key-value pairs, not just items. Tuples are immutable and cannot be changed.

3. Final Answer:

   Use a list because it keeps order and allows adding/removing items -> Option C

4. Quick Check:

   Lists keep order and are changeable [OK]

Hint: Lists keep order and allow changes, perfect for student lists [OK]

Common Mistakes:

• Choosing sets which don't keep order
• Confusing dictionaries with lists
• Using tuples which cannot be changed