Shuffling arrays in NumPy - Time & Space Complexity

Time Complexity: Shuffling arrays

O(n)

Understanding Time Complexity

We want to understand how the time it takes to shuffle an array changes as the array gets bigger.

Specifically, how does the work grow when we shuffle more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.arange(1_000_000)
np.random.shuffle(arr)

This code creates an array of one million numbers and then shuffles them randomly.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Swapping elements in the array during the shuffle.
• How many times: Each element is visited once to swap with another element.

How Execution Grows With Input

As the array size grows, the number of swaps grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 10 swaps
100	About 100 swaps
1000	About 1000 swaps

Pattern observation: The work grows linearly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to shuffle grows directly in proportion to the array size.

Common Mistake

[X] Wrong: "Shuffling takes the same time no matter how big the array is."

[OK] Correct: Actually, each element must be swapped once, so bigger arrays take more time.

Interview Connect

Knowing how shuffling scales helps you understand data preparation steps in real projects and shows you can analyze common array operations.

Self-Check

"What if we shuffled a 2D array instead of a 1D array? How would the time complexity change?"