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?"

Practice

1. What does the np.dot() function do when applied to two 1D arrays (vectors)?

easy

A. Multiplies each element of the first array by the second array as a whole.

B. Adds the two arrays element-wise.

C. Returns the cross product of the two vectors.

D. Calculates the sum of products of corresponding elements (dot product).

Solution

1. Step 1: Understand np.dot() with 1D arrays

   When given two 1D arrays, np.dot() multiplies each pair of elements and sums them up.

2. Step 2: Compare with other operations

   Adding element-wise or cross product are different operations; np.dot() specifically does the sum of products.

3. Final Answer:

   Calculates the sum of products of corresponding elements (dot product). -> Option D

4. Quick Check:

   np.dot(vector1, vector2) = sum of element-wise products [OK]

Hint: Dot product sums element-wise multiplications [OK]

Common Mistakes:

• Confusing dot product with element-wise addition
• Thinking np.dot() returns cross product for 1D arrays
• Assuming np.dot() multiplies arrays element-wise without summing

2. Which of the following is the correct syntax for the np.dot() function to compute the dot product of two numpy arrays a and b?

easy

A. np.dot(a, b)

B. a.dot(b)

C. np.dot(a + b)

D. np.dot(a * b)

Solution

1. Step 1: Recall np.dot() syntax

   The function np.dot() takes two arguments: the first and second arrays to multiply.

2. Step 2: Check each option

   np.dot(a, b) correctly calls np.dot(a, b). a.dot(b) is valid but uses method syntax, not the function. Options A and C misuse the function by passing one argument or element-wise multiplication.

3. Final Answer:

   np.dot(a, b) -> Option A

4. Quick Check:

   np.dot(array1, array2) is correct syntax [OK]

Hint: Use np.dot(a, b) with two arguments [OK]

Common Mistakes:

• Passing only one argument to np.dot()
• Using addition or multiplication inside np.dot() incorrectly
• Confusing method call with function call

3. What is the output of the following code?

import numpy as np
x = np.array([1, 2, 3])
y = np.array([4, 5, 6])
result = np.dot(x, y)
print(result)

medium

A. [4 10 18]

B. 32

C. 15

D. Error

Solution

1. Step 1: Calculate element-wise products

   Multiply corresponding elements: 1*4=4, 2*5=10, 3*6=18.

2. Step 2: Sum the products

   Sum: 4 + 10 + 18 = 32.

3. Final Answer:

   32 -> Option B

4. Quick Check:

   Sum of products = 32 [OK]

Hint: Multiply and sum elements for dot product [OK]

Common Mistakes:

• Printing element-wise multiplication instead of sum
• Confusing dot product with addition
• Expecting a vector output instead of a scalar

4. Identify the error in this code snippet:

import numpy as np
A = np.array([[1, 2], [3, 4]])
B = np.array([5, 6, 7])
result = np.dot(A, B)
print(result)

medium

A. Syntax error in np.dot() call.

B. np.dot() requires three arguments.

C. Shape mismatch: cannot multiply 2x2 matrix with length 3 vector.

D. No error; output is [17 39].

Solution

1. Step 1: Check shapes of arrays

   Matrix A is 2x2, vector B has length 3. For dot product, inner dimensions must match.

2. Step 2: Identify mismatch

   2 (columns of A) does not equal 3 (length of B), so multiplication is invalid.

3. Final Answer:

   Shape mismatch: cannot multiply 2x2 matrix with length 3 vector. -> Option C

4. Quick Check:

   Matrix columns must match vector length [OK]

Hint: Check matrix columns match vector length [OK]

Common Mistakes:

• Ignoring shape mismatch and expecting output
• Thinking np.dot() can auto-adjust shapes
• Confusing syntax error with shape error

5. Given two matrices:

A = np.array([[1, 0, 2], [3, 1, 0]])
B = np.array([[2, 1], [0, 3], [1, 4]])

What is the result of np.dot(A, B)?

hard

A. [[4 9]
[6 6]]

B. [[2 1 8]
[6 3 0]]

C. [[2 1]
[0 3]
[1 4]]

D. Error due to shape mismatch

Solution

1. Step 1: Verify shapes for multiplication

   A is 2x3, B is 3x2, so multiplication is valid (3 matches 3).

2. Step 2: Calculate dot product manually

   Row 1 of A and column 1 of B: 1*2 + 0*0 + 2*1 = 2 + 0 + 2 = 4
   Row 1 of A and column 2 of B: 1*1 + 0*3 + 2*4 = 1 + 0 + 8 = 9
   Row 2 of A and column 1 of B: 3*2 + 1*0 + 0*1 = 6 + 0 + 0 = 6
   Row 2 of A and column 2 of B: 3*1 + 1*3 + 0*4 = 3 + 3 + 0 = 6

3. Final Answer:

   [[4 9] [6 6]] -> Option A

4. Quick Check:

   Matrix multiplication sums products of rows and columns [OK]

Hint: Multiply rows of A by columns of B and sum [OK]

Common Mistakes:

• Mixing up rows and columns during multiplication
• Expecting element-wise multiplication output
• Ignoring shape compatibility rules