Time complexity analysis helps us determine how much more time our algorithm needs to solve a bigger problem.

In this article, I will explain what Big O notation means in time complexity analysis. We'll look at three different algorithms for checking if a number is prime, and we'll use Big O notation to analyze the time complexity of these algorithms.

## What does Big O Notation Mean?

Big O notation describes how an algorithm's estimated runtime increases when we increase the size of the problem we are solving.

Let's consider some hypothetical algorithms for sorting a list of numbers.

If we have an `O(n)`

algorithm for sorting a list, the amount of time we take increases linearly as we increase the size of our list.

A list that has 10 times as many numbers will take approximately 10 times as long to sort. This means that if sorting `10`

numbers takes us `4`

seconds, then we would expect sorting a list of `100`

numbers to take us approximately `40`

seconds.

If we instead have an `O(n²)`

algorithm for sorting a list, then we should expect that the amount of time we take will increase quadratically as we increase the size of our list.

A list that has `10`

times as many numbers will take approximately `100`

times as long to sort! This means that if sorting `10`

numbers takes us `4`

seconds, then we would expect sorting a list of `100`

numbers to take us approximately `400`

seconds.

The fastest algorithms for sorting a list are actually `O(n log(n))`

.

With these algorithms, we can expect that a list with `10`

times as many numbers will take approximately `23`

times as long to sort.

In other words, if sorting `10`

numbers takes us `4`

seconds, then we would expect sorting a list of `100`

numbers to take us approximately `92`

seconds.

## Big O Example - Prime Number Checker

Now that we know what Big O notation tells us, let's look at how we use Big O notation in time complexity analysis.

In this section, we will look at three different algorithms for checking if a number is *prime*. By the definition of a *prime* number, `num`

is *prime* if the only numbers that divide evenly into `num`

are `1`

and `num`

itself.

### Algorithm 1 - Check All Possible Divisors

The simplest algorithm I can think of to check if a number is *prime* is to check for any divisors other than `1`

and `num`

itself.

In the `is_prime_all()`

function below, I try dividing every number between `1`

and `num`

into `num`

and check for a remainder.

I wrote this code in Rust so I could use criterion to benchmark the runtime, but time complexity analysis with Big O notation works the same way with every programming language.

If you want to run criterion with this code on your computer, you can find the Rust source code on GitHub.

```
pub fn is_prime_all(num: i64) -> bool {
// Check for divisors of num
for i in 2..num {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
```

We have to check `num - 2`

different numbers with this algorithm before we can say that `num`

is prime, so this algorithm has time complexity of `O(num)`

or `O(n)`

.

You probably noticed that we removed the `-2`

from our Big O notation. When we are calculating the time complexity in Big O notation for an algorithm, we only care about the biggest factor of `num`

in our equation, so all smaller terms are removed.

When I tested my function, it took my computer an average of `5.9`

microseconds to verify that `1,789`

is prime and an average of `60.0`

microseconds to verify that `17,903`

is prime.

This means that it takes approximately `10`

times longer to check a number that is `10`

times larger, which we expected from our time complexity analysis!

### Algorithm 2 - Check Half of the Possible Divisors

We can improve our algorithm. If our number, `num`

, is not divisible by `2`

, then we also know that our number can't be divisible by `num/2`

or any larger number. This means we can check fewer numbers:

```
pub fn is_prime_half(num: i64) -> bool {
// Check for divisors of num
for i in 2..num / 2 {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
```

This code takes half as long to run. On my computer, it only takes `3.1`

microseconds to verify that `1,789`

is prime. Unfortunately, it takes `31.1`

microseconds to verify that `17,903`

is prime, which means that the time complexity of our algorithm did not change!

This is because our largest factor of `num`

was the same in the time complexity of our new algorithm. We need to check `num/2 - 1`

values, which means that our algorithm is still `O(n)`

.

### Algorithm 3 - Check all Possible Divisor Pairs

Let's try a third algorithm and see if we can get a smaller time complexity.

For this algorithm, we will improve upon our second algorithm. In algorithm 2, we use the fact that if `2`

is not a divisor of our number, `num`

, then `num/2`

can't be a divisor either.

But this is not a special trick we can only do with `2`

. If `3`

is not a divisor of our number, then `num/3`

also can't be a divisor. If `4`

is not a divisor of our number, then `num/4`

can't be a divisor either.

The biggest number we need to check is `√num`

, because `√num * √num = num.`

```
pub fn is_prime_sqrt(num: i64) -> bool {
// Check for divisors of num
for i in 2..=(num as f64).sqrt() as i64 {
if num % i == 0 {
// Any divisor other than 1 or num means num is not prime
return false;
}
}
// No other divisors found means num is prime
return true;
}
```

We are only checking `√num - 1`

different numbers, so this means that our time complexity should be `O(√n)`

. When I run this on my computer, I see that it takes only `161.9`

nanoseconds to check that `1,789`

is prime and `555.0`

nanoseconds to check that `17,903`

is prime.

This means it took approximately `3.4`

times longer to check a number that is `10`

times larger, and `√10 ≈ 3.2`

. Our complexity analysis accurately estimates how much longer it takes to check bigger prime numbers with this algorithm.

## Summary

Time complexity analysis helps us determine how much more time our algorithm needs to solve a bigger problem.

We looked at what Big O notation means in time complexity analysis, and we used Big O notation to analyze the time complexity of three primality checking algorithms.