Time Complexity: Why advanced indexing matters
O(n)
0
0
Why advanced indexing matters in NumPy - Performance Analysis
Understanding Time Complexity
We want to see how using advanced indexing in numpy affects the time it takes to get data.
How does the time grow when we pick many items from an array in different ways?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
import numpy as np
arr = np.arange(1000000)
indices = np.random.randint(0, 1000000, size=10000)
result = arr[indices]This code picks 10,000 items from a large array using advanced indexing with a list of random positions.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Accessing elements at each index in the indices array.
- How many times: Once for each index in the indices list (10,000 times here).
How Execution Grows With Input
As the number of indices grows, the time to get elements grows roughly the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 element accesses |
| 100 | About 100 element accesses |
| 1000 | About 1000 element accesses |
Pattern observation: The time grows directly with how many items you pick.
Final Time Complexity
Time Complexity: O(n)
This means the time to get elements grows in a straight line with the number of indices you use.
Common Mistake
[X] Wrong: "Advanced indexing is instant no matter how many items I pick."
[OK] Correct: Each index requires accessing the array, so more indices mean more work and more time.
Interview Connect
Understanding how indexing time grows helps you write faster code and explain your choices clearly in real projects.
Self-Check
"What if we used slicing instead of advanced indexing? How would the time complexity change?"