Fancy indexing with integer arrays in NumPy - Time & Space Complexity

Time Complexity: Fancy indexing with integer arrays

O(n)

Understanding Time Complexity

We want to understand how the time needed to pick elements using fancy indexing changes as the size of the index array grows.

How does the work grow when we select many elements at once?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1000000)
indices = np.array([10, 500, 999999, 12345, 67890])
selected = arr[indices]

This code picks elements from a large array using a smaller array of integer positions.

Identify Repeating Operations

• Primary operation: Accessing elements at each index in the integer array.
• How many times: Once for each index in the indices array.

How Execution Grows With Input

Each element requested requires one access operation, so the total work grows directly with the number of indices.

Input Size (n)	Approx. Operations
10	10 element accesses
100	100 element accesses
1000	1000 element accesses

Pattern observation: Doubling the number of indices doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to select elements grows linearly with the number of indices you use.

Common Mistake

[X] Wrong: "Fancy indexing is instant no matter how many indices I use."

[OK] Correct: Each index requires accessing the array, so more indices mean more work and more time.

Interview Connect

Understanding how indexing scales helps you explain data selection efficiency and choose the right approach when working with large datasets.

Self-Check

What if we changed the indices array to a boolean mask of the same size? How would the time complexity change?