Check if Number is Prime in DSA Python - Time & Space Complexity

Time Complexity: Check if Number is Prime

O(n)

Understanding Time Complexity

We want to understand how the time to check if a number is prime grows as the number gets bigger.

Specifically, how many steps does it take to decide if a number has any divisors?

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, n):
        if n % i == 0:
            return False
    return True
    

This code checks if a number n is prime by testing all numbers from 2 up to n-1 for divisibility.

Identify Repeating Operations

• Primary operation: The for-loop that tests divisibility from 2 to n-1.
• How many times: Up to n-2 times in the worst case (when n is prime).

How Execution Grows With Input

As the number n grows, the number of divisibility checks grows roughly the same as n.

Input Size (n)	Approx. Operations
10	Up to 8 checks
100	Up to 98 checks
1000	Up to 998 checks

Pattern observation: The number of steps grows roughly in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

This means the time to check if a number is prime grows directly with the size of the number.

Common Mistake

[X] Wrong: "Checking divisibility up to n/2 is enough and faster than checking up to n."

[OK] Correct: While checking up to n/2 reduces steps, it is still linear and not optimal. The best known simple method checks only up to the square root of n, which is much faster.

Interview Connect

Understanding this time complexity helps you explain how to improve prime checks and shows you can analyze simple loops clearly.

Self-Check

"What if we change the loop to run only up to the square root of n? How would the time complexity change?"