Connected component labeling in SciPy - Time & Space Complexity

Time Complexity: Connected component labeling

O(n)

Understanding Time Complexity

When we label connected parts in an image or grid, we want to know how long it takes as the image grows.

We ask: How does the time needed change when the image size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.ndimage import label

image = np.array([
    [1, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 1, 1],
    [0, 0, 1, 1]
])

labeled_array, num_features = label(image)
    

This code finds and labels connected groups of 1s in a 2D array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each pixel and checking neighbors to assign labels.
• How many times: Each pixel is visited at least once, and neighbor checks happen for each pixel.

How Execution Grows With Input

As the image size grows, the number of pixels grows, so the work grows roughly with the number of pixels.

Input Size (n = total pixels)	Approx. Operations
10 (e.g., 2x5)	About 10 pixel checks + neighbor checks
100 (10x10)	About 100 pixel checks + neighbor checks
1024 (32x32)	About 1024 pixel checks + neighbor checks

Pattern observation: The operations increase roughly in direct proportion to the number of pixels.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows linearly with the number of pixels in the image.

Common Mistake

[X] Wrong: "The labeling takes quadratic time because it checks neighbors for each pixel multiple times."

[OK] Correct: The algorithm uses efficient methods like union-find or scanning that avoid repeated full checks, so each pixel and its neighbors are processed a limited number of times, keeping time linear.

Interview Connect

Understanding how connected component labeling scales helps you explain image processing tasks clearly and shows you can analyze real data problems efficiently.

Self-Check

"What if we changed the connectivity from 4-neighbors to 8-neighbors? How would the time complexity change?"