Convex hull computation in SciPy - Time & Space Complexity

Time Complexity: Convex hull computation

O(n log n)

Understanding Time Complexity

We want to understand how the time to find the convex hull changes as we add more points.

How does the work grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.spatial import ConvexHull
import numpy as np

points = np.random.rand(1000, 2)  # 1000 points in 2D
hull = ConvexHull(points)
    

This code computes the convex hull of 1000 random points in 2D space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking and comparing points to build the hull boundary.
• How many times: Depends on the number of input points and the hull size; the algorithm processes points multiple times to find the outer boundary.

How Execution Grows With Input

As the number of points increases, the time to compute the hull grows a bit faster than the number of points.

Input Size (n)	Approx. Operations
10	About 30 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: The operations grow roughly proportional to n log n, which means it grows faster than n but slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to find the convex hull grows a bit faster than the number of points, but not too fast.

Common Mistake

[X] Wrong: "Computing the convex hull takes the same time no matter how many points there are."

[OK] Correct: More points mean more comparisons and checks, so the work grows as the input grows.

Interview Connect

Understanding how the convex hull algorithm scales helps you explain your approach clearly and shows you know how input size affects performance.

Self-Check

"What if the points were already sorted or arranged in a circle? How would the time complexity change?"