Why Math and Number Theory Appear in DSA Problems in DSA Python - Performance Analysis

Time Complexity: Why Math and Number Theory Appear in DSA Problems

O(√n)

Understanding Time Complexity

Math and number theory often show up in coding problems because they help us find efficient ways to solve puzzles involving numbers.

We want to understand how the time to solve these problems grows as the numbers get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def is_prime(n: int) -> bool:
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

This code checks if a number is prime by testing divisors up to its square root.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop checking divisors from 2 up to √n.
• How many times: Approximately √n times for input n.

How Execution Grows With Input

As the number n grows, the number of checks grows roughly with the square root of n.

Input Size (n)	Approx. Operations
10	About 3 checks (2,3)
100	About 10 checks (2 to 10)
1000	About 31 checks (2 to 31)

Pattern observation: The number of operations grows slower than n, roughly like the square root of n.

Final Time Complexity

Time Complexity: O(√n)

This means the time to check if a number is prime grows roughly with the square root of the number.

Common Mistake

[X] Wrong: "We need to check all numbers from 2 up to n-1 to find if n is prime."

[OK] Correct: Checking up to n-1 is unnecessary because any factor larger than √n pairs with a smaller factor already checked.

Interview Connect

Understanding how math helps reduce the number of steps in problems is a key skill that shows you can write efficient code, which is important in interviews.

Self-Check

"What if we used a sieve method to find primes up to n? How would the time complexity change?"