Generating random samples in NumPy - Time & Space Complexity

Time Complexity: Generating random samples

O(n)

Understanding Time Complexity

We want to understand how the time needed to create random samples changes as we ask for more samples.

How does the work grow when we increase the number of random values generated?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

# Generate n random samples from a normal distribution
n = 1000
samples = np.random.normal(loc=0, scale=1, size=n)

This code creates an array of n random numbers from a normal distribution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating each random number in the array.
• How many times: Exactly n times, once for each sample requested.

How Execution Grows With Input

As we ask for more samples, the time to generate them grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 random number generations
100	About 100 random number generations
1000	About 1000 random number generations

Pattern observation: Doubling the number of samples roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to generate samples grows linearly with the number of samples requested.

Common Mistake

[X] Wrong: "Generating 1000 samples takes the same time as generating 10 samples because it's just one function call."

[OK] Correct: Each sample requires work, so more samples mean more time, even if it's one call.

Interview Connect

Understanding how time grows with input size helps you explain performance clearly and shows you can think about efficiency in real tasks.

Self-Check

"What if we generate samples in batches of fixed size instead of all at once? How would the time complexity change?"

Practice

1. What does the numpy.random.choice function do?

easy

A. It calculates the mean of an array.

B. It selects random elements from a given array or list.

C. It sorts an array in ascending order.

D. It reshapes an array into a new shape.

Solution

1. Step 1: Understand the function purpose

   numpy.random.choice is designed to pick random elements from a given array or list.

2. Step 2: Compare with other options

   Sorting, calculating mean, and reshaping are different numpy functions, not related to random sampling.

3. Final Answer:

   It selects random elements from a given array or list. -> Option B

4. Quick Check:

   Random sampling = selecting elements randomly [OK]

Hint: Remember: choice means picking randomly from data [OK]

Common Mistakes:

• Confusing choice with sorting or reshaping functions
• Thinking it calculates statistics like mean
• Assuming it modifies array shape

2. Which of the following is the correct syntax to randomly select 3 elements from array arr without replacement using numpy?

easy

A. numpy.random.choice(arr, 3, replace=True)

B. numpy.choice(arr, size=3, replace=False)

C. numpy.random.choice(arr, size=3, replace=False)

D. numpy.random.choice(arr, size=3, replace=True)

Solution

1. Step 1: Identify correct function and parameters

   The function is numpy.random.choice. To select 3 elements without replacement, use size=3 and replace=False.

2. Step 2: Check each option

   numpy.random.choice(arr, size=3, replace=False) uses correct function and parameters. numpy.random.choice(arr, 3, replace=True) uses replacement True (wrong). numpy.choice(arr, size=3, replace=False) uses wrong function name. numpy.random.choice(arr, size=3, replace=True) uses replacement True (wrong).

3. Final Answer:

   numpy.random.choice(arr, size=3, replace=False) -> Option C

4. Quick Check:

   Correct syntax = choice + size + replace=False [OK]

Hint: Use replace=False to avoid repeated picks [OK]

Common Mistakes:

• Using replace=True when no repeats wanted
• Misspelling function name as numpy.choice
• Passing size as positional without keyword

3. What is the output of this code?

import numpy as np
np.random.seed(0)
arr = np.array([10, 20, 30, 40])
sample = np.random.choice(arr, size=2, replace=False)
sample_sorted = np.sort(sample)
sample_sorted.tolist()

medium

A. [10, 40]

B. [10, 20]

C. [20, 40]

D. [30, 40]

Solution

1. Step 1: Understand random seed and choice

   Setting seed to 0 fixes randomness. Using choice with size=2 and replace=False picks 2 unique elements from [10,20,30,40].

2. Step 2: Determine chosen elements and sort

   With seed 0, the chosen elements are [10, 40]. Sorting gives [10, 40].

3. Final Answer:

   [10, 40] -> Option A

4. Quick Check:

   Seed 0 + choice + sort = [10, 40] [OK]

Hint: Seed fixes output; sort to order chosen elements [OK]

Common Mistakes:

• Ignoring seed and expecting different output
• Not sorting before converting to list
• Assuming replacement allows duplicates

4. The following code throws an error. What is the cause?

import numpy as np
arr = np.array([1, 2, 3])
sample = np.random.choice(arr, size=5, replace=False)

medium

A. Incorrect function name used.

B. Array contains integers instead of floats.

C. Missing import statement for numpy.

D. Size is larger than array length without replacement.

Solution

1. Step 1: Analyze parameters and array size

   The array has 3 elements, but size=5 is requested without replacement.

2. Step 2: Understand replacement=False effect

   Without replacement, you cannot pick more elements than exist. This causes a ValueError.

3. Final Answer:

   Size is larger than array length without replacement. -> Option D

4. Quick Check:

   Sampling more than available without replace=False causes error [OK]

Hint: Check if sample size > array length when replace=False [OK]

Common Mistakes:

• Assuming replacement=True by default
• Ignoring array length vs sample size
• Thinking data type causes error

5. You want to simulate rolling a weighted 6-sided die 10 times using numpy, where side 6 is twice as likely as others. Which code correctly generates this sample?

hard

A. np.random.choice([1,2,3,4,5,6], size=10, replace=True, p=[1/7,1/7,1/7,1/7,1/7,2/7])

B. np.random.choice([1,2,3,4,5,6], size=10, replace=False, p=[1/6]*6)

C. np.random.choice([1,2,3,4,5,6], size=10, replace=True)

D. np.random.choice([1,2,3,4,5,6], size=10, replace=True, p=[1/6,1/6,1/6,1/6,1/6,1/6])

Solution

1. Step 1: Understand weighted probabilities

   Side 6 should be twice as likely, so probabilities sum to 1 with side 6 having weight 2/7 and others 1/7 each.

2. Step 2: Check sampling parameters

   Sampling 10 times with replacement is needed to allow repeats. np.random.choice([1,2,3,4,5,6], size=10, replace=True, p=[1/7,1/7,1/7,1/7,1/7,2/7]) uses correct probabilities and replace=True.

3. Step 3: Verify other options

   The code with replace=False, p=[1/6]*6 incorrectly prevents repeats needed for multiple rolls. The codes with uniform probabilities (explicit [1/6,1/6,1/6,1/6,1/6,1/6] or none specified) do not weight side 6 twice as likely.

4. Final Answer:

   np.random.choice([1,2,3,4,5,6], size=10, replace=True, p=[1/7,1/7,1/7,1/7,1/7,2/7]) -> Option A

5. Quick Check:

   Weighted probabilities + replace=True for repeated rolls [OK]

Hint: Use p= with weights summing to 1 and replace=True [OK]

Common Mistakes:

• Using replace=False for multiple rolls
• Not setting probabilities for weighted sides
• Using equal probabilities when weights differ