np.dot() for dot product in NumPy - Time & Space Complexity

Time Complexity: np.dot() for dot product

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate a dot product changes as the size of the input arrays grows.

Specifically, how does the work increase when we multiply bigger vectors or matrices?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

# Create two vectors of size n
n = 1000
vector_a = np.random.rand(n)
vector_b = np.random.rand(n)

# Compute their dot product
result = np.dot(vector_a, vector_b)

This code calculates the dot product of two vectors, which means multiplying each pair of elements and adding all those products together.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each element of the first vector by the corresponding element of the second vector, then summing all results.
• How many times: Once for each element in the vectors, so n times.

How Execution Grows With Input

As the size of the vectors grows, the number of multiplications and additions grows at the same rate.

Input Size (n)	Approx. Operations
10	About 10 multiplications and 9 additions
100	About 100 multiplications and 99 additions
1000	About 1000 multiplications and 999 additions

Pattern observation: The total work grows roughly in direct proportion to the size of the vectors.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the dot product grows linearly with the size of the input vectors.

Common Mistake

[X] Wrong: "The dot product takes constant time because it's just one function call."

[OK] Correct: Even though it's one function call, the function must multiply and add each pair of elements, so the time depends on the vector size.

Interview Connect

Understanding how the dot product scales helps you reason about performance in many data science tasks, like similarity calculations or matrix operations.

Self-Check

"What if we changed the vectors to matrices and used np.dot() to multiply them? How would the time complexity change?"