Monte Carlo simulation basics in NumPy - Time & Space Complexity

Time Complexity: Monte Carlo simulation basics

O(n)

Understanding Time Complexity

We want to understand how the time needed for a Monte Carlo simulation changes as we increase the number of random samples.

How does the number of samples affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n_samples = 1000000
random_points = np.random.rand(n_samples, 2)
distances = np.sqrt(random_points[:, 0]**2 + random_points[:, 1]**2)
inside_circle = distances <= 1
estimate = 4 * np.sum(inside_circle) / n_samples
print(estimate)

This code estimates the value of pi by randomly sampling points inside a square and checking how many fall inside a quarter circle.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating and checking each random point.
• How many times: Once for each of the n_samples points.

How Execution Grows With Input

As we increase the number of samples, the work grows roughly in direct proportion.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows linearly with the number of random points sampled.

Common Mistake

[X] Wrong: "The time grows faster than the number of samples because of the square root calculation."

[OK] Correct: The square root is done once per point, so it adds a constant amount of work per sample, keeping growth linear overall.

Interview Connect

Understanding how sampling size affects runtime helps you explain trade-offs between accuracy and speed in simulations.

Self-Check

What if we used a nested loop to generate points in a grid instead of random sampling? How would the time complexity change?

Practice

1. What is the main purpose of a Monte Carlo simulation in data science?

easy

A. To create visual charts

B. To sort data quickly

C. To estimate results using random sampling

D. To clean missing data

Solution

1. Step 1: Understand Monte Carlo simulation basics

   Monte Carlo simulation uses random sampling to estimate results when exact calculation is hard.

2. Step 2: Identify the main purpose

   It helps estimate outcomes by simulating many random scenarios.

3. Final Answer:

   To estimate results using random sampling -> Option C

4. Quick Check:

   Monte Carlo = random sampling estimation [OK]

Hint: Monte Carlo = random sampling for estimation [OK]

Common Mistakes:

• Confusing Monte Carlo with data sorting
• Thinking it cleans data
• Assuming it creates charts

2. Which numpy function is commonly used to generate random samples for Monte Carlo simulations?

easy

A. numpy.random.rand()

B. numpy.array()

C. numpy.mean()

D. numpy.sort()

Solution

1. Step 1: Identify numpy functions for randomness

   numpy.random.rand() generates random numbers between 0 and 1, useful for sampling.

2. Step 2: Compare with other options

   numpy.array() creates arrays, numpy.mean() calculates average, numpy.sort() sorts data; none generate random samples.

3. Final Answer:

   numpy.random.rand() -> Option A

4. Quick Check:

   Random samples = numpy.random.rand() [OK]

Hint: Random samples come from numpy.random.rand() [OK]

Common Mistakes:

• Choosing numpy.array() instead of random function
• Confusing mean or sort with random sampling
• Using functions that don't generate randomness

3. What is the output of this code snippet?

import numpy as np
np.random.seed(0)
samples = np.random.rand(5)
mean_val = np.mean(samples)
print(round(mean_val, 2))

medium

A. 0.50

B. 0.57

C. 0.60

D. 0.45

Solution

1. Step 1: Generate 5 random samples with seed 0

   Using np.random.seed(0) fixes randomness. np.random.rand(5) produces [0.5488135, 0.71518937, 0.60276338, 0.54488318, 0.4236548].

2. Step 2: Calculate mean and round

   Sum = 2.83530423, mean = 0.567060846, round(mean_val, 2) = 0.57.

3. Final Answer:

   0.57 -> Option B

4. Quick Check:

   Mean of samples = 0.57 [OK]

Hint: Seed fixes random values; mean rounds to 0.57 [OK]

Common Mistakes:

• Not setting seed causing different outputs
• Rounding incorrectly
• Calculating sum or mean wrongly

4. Identify the error in this Monte Carlo simulation code:

import numpy as np
samples = np.random.rand(1000)
result = sum(samples) / 100
print(result)

medium

A. Using np.random.rand() instead of np.random.randint()

B. Not setting random seed

C. Missing np.mean() function

D. Dividing by 100 instead of number of samples

Solution

1. Step 1: Check calculation of average

   sum(samples) sums 1000 values, but dividing by 100 underestimates average.

2. Step 2: Correct divisor

   To get average, divide sum by 1000 (number of samples), not 100.

3. Final Answer:

   Dividing by 100 instead of number of samples -> Option D

4. Quick Check:

   Average = sum / number of samples [OK]

Hint: Divide sum by sample count, not fixed number [OK]

Common Mistakes:

• Dividing by wrong number
• Confusing random functions
• Ignoring seed importance

5. You want to estimate the probability that a random point inside a 1x1 square falls within a circle of radius 0.5 centered at (0.5, 0.5) using Monte Carlo simulation. Which numpy code correctly estimates this probability?

hard

A. points = np.random.rand(10000, 2)
dist = np.sqrt((points[:,0]-0.5)**2 + (points[:,1]-0.5)**2)
prob = np.sum(dist <= 0.5) / 10000
print(prob)

B. points = np.random.rand(10000)
dist = np.sqrt((points-0.5)**2)
prob = np.sum(dist <= 0.5) / 10000
print(prob)

C. points = np.random.rand(2, 10000)
dist = np.sqrt((points[:,0]-0.5)**2 + (points[:,1]-0.5)**2)
prob = np.sum(dist <= 0.5) / 10000
print(prob)

D. points = np.random.randint(0, 1, (10000, 2))
dist = np.sqrt((points[:,0]-0.5)**2 + (points[:,1]-0.5)**2)
prob = np.sum(dist <= 0.5) / 10000
print(prob)

Solution

1. Step 1: Generate 2D points inside 1x1 square

   np.random.rand(10000, 2) creates 10000 points with x,y in [0,1].

2. Step 2: Calculate distance from center (0.5,0.5)

   Distance formula sqrt((x-0.5)^2 + (y-0.5)^2) applied to each point.

3. Step 3: Count points inside circle and estimate probability

   Count points with distance ≤ 0.5, divide by total points for probability.

4. Final Answer:

   np.random.rand(10000, 2) with column indexing for coordinates -> Option A

5. Quick Check:

   2D points + distance check = probability [OK]

Hint: Use 2D random points and distance formula [OK]

Common Mistakes:

• Using 1D points instead of 2D
• Wrong shape for points array
• Using randint instead of rand for floats