## Algorithm time complexity 1- what is it

In these days, we have super fast computers that can compute so fast we can’t even imagine it. So should we care about our algorithm time coplexity?

Well I hope that with little bit of math and some examples I will convince you that you should care.

## How to compute time complexity?

At first you have to know what can influence the performance of your algorithm.

– Hardware (sigle vs multi processor, read/write to memory, 32 vs 64 bit)

– **Input**

You might be little bit suprised by this, but hardware is not such a big deal. **Input is the real problem here**.

The bigger the input the more time it will take to finish.

**Here comes the demo. You can download it here.**

We have 2 algorithms

1. IsPrimeNumber

private static bool IsPrimeNumber(long number) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; }

This alghorithm will run in worst case ,when the number is a prime number and I have to iterate all numbers, (number – 2) times.

Let say that my computer is really slow and one iteration takes him 1 ms.

So this piece of code would take 21 ms for number = 23.

**Explanation:**

number-2 => 23-2 =21.

This is all just theory, because my computer and yours probably too makes it in 1 ms all.

However try to run the demo with the number = 63544753, or you can pick even bigger prime number here.

Now you can see that it takes time, quite a lot of time for 11 lines of code.

2. So we can try IsPrimeNumberFaster

private static bool IsPrimeNumberFaster(long number) { var sqrt = Math.Sqrt(number); for (int i = 2; i <= sqrt; i++) { if (number % i == 0) { return false; } } return true; }

This algorithm will run in worst case (sqrt(number) – 1) times. And that is a lot less than the first algorithm.

**Explanation:**

for number=23 it is (sqrt(number)-1) = > (sqrt(23) – 1) = 3.8.

Feel free to try my demo and you will see that this algorithm will finish much faster for number=63544753 than the first one.

From the graph of functions we can see that linear function (n-2) => O(n) grow faster than O(sqrt(n)) especially for large input (large number in our case).

**O** is so called **big-oh**. We will discuss big-oh next time.

I hope that I convinced you that time complexity of an algorithm is very important and you should think about it when you are writing your code.

Time complexity and how to count complexity of your algorithm.