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?