Distance metrics (euclidean, cosine, manhattan) in SciPy - Time & Space Complexity

Time Complexity: Distance metrics (euclidean, cosine, manhattan)

O(d)

Understanding Time Complexity

We want to know how the time to calculate distances grows as we compare more points.

How does the number of points affect the work done by distance calculations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.spatial import distance

points = [[1, 2], [3, 4], [5, 6]]

# Calculate Euclidean distance between first two points
euclidean_dist = distance.euclidean(points[0], points[1])

# Calculate Cosine distance between first two points
cosine_dist = distance.cosine(points[0], points[1])

# Calculate Manhattan distance between first two points
manhattan_dist = distance.cityblock(points[0], points[1])
    

This code calculates three types of distances between two points in 2D space.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Summing differences across each dimension of the points.
• How many times: Once per dimension for each distance calculation.

How Execution Grows With Input

As the number of dimensions grows, the work to compute distance grows linearly.

Input Size (dimensions)	Approx. Operations
10	About 10 sums and calculations
100	About 100 sums and calculations
1000	About 1000 sums and calculations

Pattern observation: Doubling dimensions roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(d)

This means the time to compute distance grows directly with the number of dimensions.

Common Mistake

[X] Wrong: "Calculating distance between two points takes the same time no matter how many dimensions they have."

[OK] Correct: Each dimension adds more numbers to process, so more dimensions mean more work.

Interview Connect

Understanding how distance calculations scale helps you explain efficiency when working with high-dimensional data.

Self-Check

"What if we calculate distances between many pairs of points instead of just one pair? How would the time complexity change?"

Practice

1. Which distance metric measures the straight-line distance between two points in space?

easy

A. Jaccard distance

B. Cosine distance

C. Manhattan distance

D. Euclidean distance

Solution

1. Step 1: Understand distance types

   Euclidean distance is the direct straight-line distance between two points.

2. Step 2: Compare with other distances

   Cosine measures angle difference, Manhattan sums absolute differences, Jaccard measures set similarity.

3. Final Answer:

   Euclidean distance -> Option D

4. Quick Check:

   Straight-line distance = Euclidean distance [OK]

Hint: Straight line means Euclidean distance [OK]

Common Mistakes:

• Confusing cosine with Euclidean
• Thinking Manhattan is straight-line
• Mixing Jaccard with numeric distances

2. Which of the following is the correct way to import the Euclidean distance function from scipy?

easy

A. from scipy.spatial.distance import euclidean

B. import scipy.distance.euclidean

C. from scipy.distance import euclidean

D. import euclidean from scipy.spatial

Solution

1. Step 1: Recall scipy import syntax

   The correct import path for distance functions is scipy.spatial.distance.

2. Step 2: Check each option

   from scipy.spatial.distance import euclidean uses correct syntax: from scipy.spatial.distance import euclidean. Others are invalid or incorrect syntax.

3. Final Answer:

   from scipy.spatial.distance import euclidean -> Option A

4. Quick Check:

   Correct import path = from scipy.spatial.distance import euclidean [OK]

Hint: Use 'from scipy.spatial.distance import' for distance functions [OK]

Common Mistakes:

• Using wrong module path
• Incorrect import syntax
• Trying to import from scipy.distance

3. What is the output of this code?

from scipy.spatial.distance import cosine
v1 = [1, 0, 1]
v2 = [0, 1, 0]
result = cosine(v1, v2)
print(round(result, 2))

medium

A. 1.0

B. 0.5

C. 0.0

D. 0.71

Solution

1. Step 1: Calculate cosine similarity basics

   Vectors v1 and v2 are orthogonal (no overlap), so cosine similarity is 0.

2. Step 2: Calculate cosine distance

   Cosine distance = 1 - cosine similarity = 1 - 0 = 1.0.

3. Final Answer:

   1.0 -> Option A

4. Quick Check:

   Orthogonal vectors cosine distance = 1.0 [OK]

Hint: Cosine distance = 1 - cosine similarity [OK]

Common Mistakes:

• Confusing cosine similarity with distance
• Rounding errors
• Assuming zero distance for orthogonal vectors

4. Find the error in this code snippet calculating Manhattan distance:

from scipy.spatial.distance import manhattan
a = [1, 2, 3]
b = [4, 5]
print(manhattan(a, b))

medium

A. Function name should be cityblock, not manhattan

B. Import statement is incorrect

C. Lists a and b must be the same length

D. Manhattan distance requires numpy arrays, not lists

Solution

1. Step 1: Check input vector lengths

   Vectors a and b have different lengths (3 and 2), which is invalid for distance calculation.

2. Step 2: Validate function and import

   Import and function name are correct; scipy.spatial.distance.manhattan is valid and accepts lists.

3. Final Answer:

   Lists a and b must be the same length -> Option C

4. Quick Check:

   Equal length vectors needed for distance [OK]

Hint: Vectors must be same length for distance functions [OK]

Common Mistakes:

• Assuming different length lists work
• Confusing function name with cityblock
• Thinking lists are invalid inputs

5. You have two points: p1 = [3, 4, 5] and p2 = [1, 1, 1]. Which distance metric will give the largest value?
Options:
A) Euclidean
B) Cosine
C) Manhattan
D) All equal

hard

A. Euclidean

B. Manhattan

C. Cosine

D. All equal

Solution

1. Step 1: Calculate Euclidean distance

   Euclidean = sqrt((3-1)^2 + (4-1)^2 + (5-1)^2) = sqrt(4 + 9 + 16) = sqrt(29) ≈ 5.39.

2. Step 2: Calculate Manhattan distance

   Manhattan = |3-1| + |4-1| + |5-1| = 2 + 3 + 4 = 9.

3. Step 3: Calculate Cosine distance

   Cosine similarity = (3*1 + 4*1 + 5*1) / (sqrt(3^2+4^2+5^2)*sqrt(1^2+1^2+1^2)) = 12 / (7.07*1.73) ≈ 0.98; Cosine distance = 1 - 0.98 = 0.02.

4. Final Answer:

   Manhattan -> Option B

5. Quick Check:

   Manhattan distance > Euclidean > Cosine distance [OK]

Hint: Manhattan sums absolute differences, usually largest [OK]

Common Mistakes:

• Assuming Euclidean is always largest
• Confusing cosine distance scale
• Ignoring absolute values in Manhattan