When NumPy is not fast enough - Time & Space Complexity

Time Complexity: When NumPy is not fast enough

O(n²)

Understanding Time Complexity

Sometimes, even fast tools like NumPy can take longer when data grows big.

We want to see how the time to run code changes as input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def pairwise_sum(arr):
    n = arr.size
    result = np.zeros(n * (n - 1) // 2)
    idx = 0
    for i in range(n):
        for j in range(i + 1, n):
            result[idx] = arr[i] + arr[j]
            idx += 1
    return result

arr = np.arange(1000)

This code calculates the sum of every pair of elements in the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops adding pairs of elements.
• How many times: The inner loop runs fewer times each outer loop, but total pairs are about n*(n-1)/2.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	45
100	4,950
1000	499,500

Pattern observation: The number of operations grows roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the input size, the work about quadruples, making it slower quickly.

Common Mistake

[X] Wrong: "NumPy always runs fast no matter what."

[OK] Correct: Even fast tools do more work when input grows, especially with nested loops causing many operations.

Interview Connect

Understanding how nested operations grow helps you explain performance and choose better methods in real projects.

Self-Check

"What if we replaced the nested loops with a vectorized NumPy operation? How would the time complexity change?"

Practice

1. Why might NumPy sometimes be too slow for certain tasks?

easy

A. Because it does not support mathematical operations

B. Because it cannot handle arrays larger than 100 elements

C. Because it only works on single-core processors

D. Because it uses Python loops internally which are slow

Solution

1. Step 1: Understand NumPy's speed basis

   NumPy is fast because it uses optimized C code, but Python loops around NumPy operations can slow it down.

2. Step 2: Identify the cause of slowness

   When complex tasks require Python loops or non-vectorized code, speed drops because Python loops are slower than compiled code.

3. Final Answer:

   Because it uses Python loops internally which are slow -> Option D

4. Quick Check:

   Python loops slow NumPy = Because it uses Python loops internally which are slow [OK]

Hint: NumPy is fast with vectorized code, slow with Python loops [OK]

Common Mistakes:

• Thinking NumPy can't handle large arrays
• Believing NumPy only works on single-core CPUs
• Assuming NumPy lacks math operation support

2. Which of the following is the correct way to import Numba to speed up NumPy code?

easy

A. import numba as nb

B. import numba.speedup

C. from numba import jit

D. import numba.jit

Solution

1. Step 1: Recall Numba import syntax

   Numba's just-in-time compiler is accessed by importing jit from numba: from numba import jit.

2. Step 2: Check other options

   Options A, C, and D are invalid imports; 'import numba as nb' imports the whole module but requires nb.jit to use the decorator, while C and D do not exist.

3. Final Answer:

   from numba import jit -> Option C

4. Quick Check:

   Correct Numba import = from numba import jit [OK]

Hint: Use 'from numba import jit' to access speedup decorator [OK]

Common Mistakes:

• Trying to import submodules that don't exist
• Importing whole numba without jit
• Using incorrect import syntax

3. What will be the output of this code snippet?

import numpy as np
from numba import jit

@jit(nopython=True)
def sum_squares(n):
    total = 0
    for i in range(n):
        total += i * i
    return total

print(sum_squares(5))

medium

A. 30

B. 55

C. 10

D. Error due to jit decorator

Solution

1. Step 1: Understand the function logic

   The function sums squares of numbers from 0 to n-1. For n=5, it sums 0²+1²+2²+3²+4² = 0+1+4+9+16 = 30.

2. Step 2: Check jit decorator effect

   The jit decorator speeds up the function but does not change output. No error occurs.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Sum of squares 0 to 4 = 30 [OK]

Hint: Sum squares 0 to 4 = 30; jit doesn't change output [OK]

Common Mistakes:

• Confusing sum of squares with sum of numbers
• Expecting jit to cause errors
• Miscounting range end

4. Identify the error in this code that tries to speed up a NumPy operation using Numba:

import numpy as np
from numba import jit

@jit
def multiply_array(arr):
    return arr * 2

print(multiply_array(np.array([1, 2, 3])))

medium

A. Numba jit cannot speed up NumPy array operations directly

B. The jit decorator is missing parentheses

C. The function multiply_array must use a loop inside

D. NumPy arrays cannot be passed to jit functions

Solution

1. Step 1: Understand Numba's limitations

   Numba jit speeds up Python loops and scalar operations but does not speed up vectorized NumPy operations directly.

2. Step 2: Analyze the code behavior

   The function returns arr * 2, which is a NumPy vectorized operation. Numba jit won't speed this up; it just calls NumPy internally.

3. Final Answer:

   Numba jit cannot speed up NumPy array operations directly -> Option A

4. Quick Check:

   Numba jit doesn't speed vectorized NumPy ops = Numba jit cannot speed up NumPy array operations directly [OK]

Hint: Numba jit speeds loops, not vectorized NumPy ops [OK]

Common Mistakes:

• Thinking jit decorator syntax is wrong
• Believing jit requires loops inside
• Assuming NumPy arrays can't be used with jit

5. You have a large NumPy array and want to speed up a custom function that applies a complex calculation element-wise. Which approach is best?

hard

A. Use pure Python loops without any acceleration

B. Rewrite the function using Numba jit with a loop over array elements

C. Convert the array to a list and use list comprehensions

D. Use NumPy vectorized operations only, no jit

Solution

1. Step 1: Understand the problem context

   Complex element-wise calculations may not be vectorizable easily with NumPy, so pure vectorized operations might not work.

2. Step 2: Choose the best speedup method

   Using Numba jit with a loop over array elements compiles the loop to fast machine code, speeding up the custom calculation.

3. Step 3: Evaluate other options

   Pure Python loops and list comprehensions are slow; vectorized NumPy ops may not support complex logic.

4. Final Answer:

   Rewrite the function using Numba jit with a loop over array elements -> Option B

5. Quick Check:

   Numba jit + loops = best speedup for complex element-wise ops [OK]

Hint: Use Numba jit with loops for complex element-wise speedup [OK]

Common Mistakes:

• Relying on pure Python loops for speed
• Converting arrays to lists unnecessarily
• Assuming all complex ops can be vectorized