List indexing and slicing in Python - Time & Space Complexity

Time Complexity: List indexing and slicing

O(1) for indexing, O(k) for slicing

Understanding Time Complexity

When working with lists, it is important to know how fast we can access or extract parts of the list.

We want to understand how the time to get an item or a slice changes as the list grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_list = list(range(1000))
item = my_list[500]       # indexing
sub_list = my_list[100:200]  # slicing

This code gets one item by index and then gets a slice (a part) of the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing one item by index and copying a slice of the list.
• How many times: Indexing accesses one element directly; slicing copies each element in the slice range.

How Execution Grows With Input

Getting one item by index takes the same time no matter how big the list is.

Getting a slice takes time proportional to how many items are in the slice.

Input Size (n)	Indexing Operations	Slicing Operations (length k)
10	1	k (e.g., 5)
100	1	k (e.g., 20)
1000	1	k (e.g., 100)

Pattern observation: Indexing time stays the same; slicing time grows with the slice size, not the whole list.

Final Time Complexity

Time Complexity: O(1) for indexing, O(k) for slicing

This means getting one item is very fast and does not depend on list size, but slicing depends on how many items you take.

Common Mistake

[X] Wrong: "Slicing a list is always as fast as indexing one item."

[OK] Correct: Slicing creates a new list by copying each item in the slice, so it takes longer if the slice is bigger.

Interview Connect

Understanding the difference between indexing and slicing helps you write efficient code and answer questions about list operations clearly.

Self-Check

"What if we slice the entire list instead of a small part? How would the time complexity change?"

Practice

1. What does the expression my_list[2] return when my_list = [10, 20, 30, 40, 50]?

easy

A. 40

B. 20

C. 30

D. 50

Solution

1. Step 1: Understand list indexing

   Indexing starts at 0, so my_list[0] is 10, my_list[1] is 20, and my_list[2] is 30.

2. Step 2: Identify the value at index 2

   The value at index 2 is 30.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Index 2 value = 30 [OK]

Hint: Remember indexing starts at zero, so count from 0 [OK]

Common Mistakes:

• Starting count from 1 instead of 0
• Confusing index 2 with index 3
• Mixing up values and indexes

2. Which of the following is the correct syntax to get the last element of a list nums using indexing?

easy

A. nums[last]

B. nums[1]

C. nums[len(nums)]

D. nums[-1]

Solution

1. Step 1: Recall negative indexing

   Negative indexes count from the end, so -1 means the last element.

2. Step 2: Check each option

   nums[-1] uses nums[-1], which correctly accesses the last element. nums[1] accesses the second element. nums[last] is invalid syntax. nums[len(nums)] causes an IndexError because list indexes go from 0 to len(nums)-1.

3. Final Answer:

   nums[-1] -> Option D

4. Quick Check:

   Last element index = -1 [OK]

Hint: Use -1 to get the last item in a list [OK]

Common Mistakes:

• Using len(nums) as index (out of range)
• Trying to use 'last' as an index
• Confusing positive and negative indexes

3. What is the output of this code?

letters = ['a', 'b', 'c', 'd', 'e']
print(letters[1:4])

medium

A. ['b', 'c', 'd']

B. ['c', 'd', 'e']

C. ['b', 'c', 'd', 'e']

D. ['a', 'b', 'c']

Solution

1. Step 1: Understand slicing syntax

   Slicing letters[1:4] means start at index 1 up to but not including index 4.

2. Step 2: Identify elements at indexes 1, 2, 3

   Index 1 is 'b', index 2 is 'c', index 3 is 'd'. So the slice is ['b', 'c', 'd'].

3. Final Answer:

   ['b', 'c', 'd'] -> Option A

4. Quick Check:

   Slicing excludes stop index [OK]

Hint: Slice stops before the stop index, not including it [OK]

Common Mistakes:

• Including the stop index element
• Confusing start and stop indexes
• Using wrong indexes for slicing

4. The code below causes an error. What is the problem?

nums = [1, 2, 3, 4, 5]
print(nums[5])

medium

A. SyntaxError due to wrong brackets

B. IndexError because index 5 is out of range

C. TypeError because nums is not a list

D. No error, prints 5

Solution

1. Step 1: Check list length and valid indexes

   List nums has 5 elements with indexes 0 to 4.

2. Step 2: Understand index 5 usage

   Index 5 is outside the valid range, so accessing nums[5] causes an IndexError.

3. Final Answer:

   IndexError because index 5 is out of range -> Option B

4. Quick Check:

   Index must be less than list length [OK]

Hint: Indexes go from 0 to length-1 only [OK]

Common Mistakes:

• Thinking index 5 is valid for 5 elements
• Confusing SyntaxError with IndexError
• Assuming list indexes start at 1

5. Given data = [5, 10, 15, 20, 25, 30], which expression returns a new list with every second element in reverse order?

hard

A. data[::-2]

B. data[::2]

C. data[-2::-1]

D. data[1::2]

Solution

1. Step 1: Understand slicing with step and negative step

   The slice data[::-2] starts from the end and takes every second element backwards.

2. Step 2: Check what data[::-2] returns

   It returns [30, 20, 10], which is every second element in reverse order.

3. Step 3: Verify other options

   data[::2] returns every second element forward: [5, 15, 25]. data[-2::-1] returns from index -2 backwards: [25, 20, 15, 10, 5]. data[1::2] returns every second element starting at index 1: [10, 20, 30].

4. Final Answer:

   data[::-2] -> Option A

5. Quick Check:

   Negative step reverses and skips elements [OK]

Hint: Use negative step to reverse and skip elements [OK]

Common Mistakes:

• Using positive step for reverse
• Confusing start index with step sign
• Misunderstanding slice boundaries