What is the time complexity of nums[5] on a Python list of 1 million items?

Options

1. O(1) (Correct option)
2. O(n)
3. O(log n)
4. O(5)

Answer

O(1)

Why

Lists are arrays, so the memory address of position 5 is calculated directly from where the list starts. It does not matter if the list has 10 or 10 million items.

That is constant time, written O(1). (O(5) is also 'constant', and Big-O drops constants, so we write O(1).)

Remember

Index access on a list = O(1).

Key terms

• Array
• Big-O notation
• Time complexity
• Index