Vectorization over loops in NumPy - Time & Space Complexity

Time Complexity: Vectorization over loops

O(n)

Understanding Time Complexity

We want to see how using vectorization instead of loops changes the time it takes to run code with numpy.

How does the work grow when we handle bigger data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 10  # Example value for n
arr = np.arange(n)
squared = arr * arr

This code creates an array of numbers and then squares each number using vectorized multiplication.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each element in the array by itself.
• How many times: Once for each element in the array, all done together using vectorized operation.

How Execution Grows With Input

As the array size grows, the time to square all elements grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	10 multiplications
100	100 multiplications
1000	1000 multiplications

Pattern observation: Doubling the input doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the operation grows linearly with the number of elements.

Common Mistake

[X] Wrong: "Vectorized operations run instantly no matter the input size."

[OK] Correct: Vectorization speeds things up by doing many operations at once, but it still needs to process each element, so time grows with input size.

Interview Connect

Understanding how vectorization changes time complexity helps you write faster code and explain your choices clearly in real projects.

Self-Check

"What if we replaced vectorized multiplication with a Python for-loop to square each element? How would the time complexity change?"

Practice

1. What is the main advantage of using vectorization in numpy instead of loops?

easy

A. It makes the code run faster by doing many operations at once.

B. It uses more memory but slows down the code.

C. It makes the code harder to read and understand.

D. It requires writing more lines of code.

Solution

1. Step 1: Understand vectorization concept

   Vectorization means applying operations on whole arrays at once, not one element at a time.

2. Step 2: Compare speed and simplicity

   This approach uses optimized numpy functions that run faster than explicit loops.

3. Final Answer:

   It makes the code run faster by doing many operations at once. -> Option A

4. Quick Check:

   Vectorization = faster code [OK]

Hint: Vectorization speeds up code by handling arrays at once [OK]

Common Mistakes:

• Thinking vectorization slows code
• Believing vectorization needs more code
• Confusing vectorization with loops

2. Which of the following numpy codes correctly replaces a loop to add 5 to each element in array a?

easy

A. a + 5

B. for i in a: i = i + 5

C. np.add(a, 5, out=a)

D. a.append(5)

Solution

1. Step 1: Identify vectorized addition

   Using np.add(a, 5, out=a) adds 5 to every element in array a efficiently.

2. Step 2: Check other options

   a + 5 works but returns a new array, for i in a: i = i + 5 does not change a, and a.append(5) is invalid for numpy arrays.

3. Final Answer:

   np.add(a, 5, out=a) -> Option C

4. Quick Check:

   np.add = vectorized add [OK]

Hint: Use numpy functions like np.add for vectorized operations [OK]

Common Mistakes:

• Using loops that don't modify array
• Trying list methods on numpy arrays
• Confusing array addition with append

3. What is the output of this code?

import numpy as np
arr = np.array([1, 2, 3])
result = arr * 2
print(result)

medium

A. [2 4 6]

B. [1 2 3 1 2 3]

C. [3 4 5]

D. Error: cannot multiply array by int

Solution

1. Step 1: Understand array multiplication

   Multiplying a numpy array by a number multiplies each element by that number.

2. Step 2: Calculate element-wise multiplication

   Each element in [1, 2, 3] is multiplied by 2, resulting in [2, 4, 6].

3. Final Answer:

   [2 4 6] -> Option A

4. Quick Check:

   Array * number = element-wise multiply [OK]

Hint: Array * number multiplies each element [OK]

Common Mistakes:

• Thinking it concatenates arrays
• Expecting an error on multiplication
• Confusing element-wise with matrix multiply

4. Identify the error in this code that tries to add 10 to each element of arr using a loop:

import numpy as np
arr = np.array([1, 2, 3])
for i in arr:
    i = i + 10
print(arr)

medium

A. Syntax error in for loop.

B. Loop variable i does not modify original array elements.

C. Array arr is not defined.

D. Cannot add integer to numpy array elements.

Solution

1. Step 1: Understand loop variable behavior

   Variable i is a copy of each element, so changing i does not change arr.

2. Step 2: Explain why array remains unchanged

   The original array arr stays the same because the loop does not assign back to array elements.

3. Final Answer:

   Loop variable i does not modify original array elements. -> Option B

4. Quick Check:

   Loop var copy ≠ array change [OK]

Hint: Loop vars are copies; assign to array to change [OK]

Common Mistakes:

• Assuming loop changes array automatically
• Thinking syntax error exists
• Believing numpy disallows int addition

5. You have a numpy array data = np.array([1, 2, 3, 4, 5]). You want to create a new array where each element is squared if it is even, otherwise doubled. Which vectorized code achieves this?

hard

A. data * 2 if data % 2 else data ** 2

B. [x**2 if x%2==0 else x*2 for x in data]

C. for i in range(len(data)): data[i] = data[i]**2 if data[i]%2==0 else data[i]*2

D. np.where(data % 2 == 0, data**2, data*2)

Solution

1. Step 1: Understand vectorized conditional with np.where

   np.where(condition, x, y) returns array choosing x where condition is true, else y.

2. Step 2: Apply condition for even and odd elements

   Condition data % 2 == 0 checks even numbers; squares them, else doubles.

3. Step 3: Check other options

   [x**2 if x%2==0 else x*2 for x in data] uses list comprehension (not vectorized), C uses loop (not vectorized), D is invalid syntax.

4. Final Answer:

   np.where(data % 2 == 0, data**2, data*2) -> Option D

5. Quick Check:

   np.where = vectorized if-else [OK]

Hint: Use np.where for vectorized if-else conditions [OK]

Common Mistakes:

• Using loops or list comprehensions instead of vectorization
• Writing invalid syntax for conditional operations
• Confusing element-wise operations with scalar