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 complexity?

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 (single vs multi processor, read/write to memory, 32 vs 64 bit)
• Input

You might be a little bit surprised 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 algorithm will run in worst case, when the number is a prime number and I have to iterate all numbers, (number – 2) times.

Let's say that my computer is really slow and one iteration takes 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 an 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
• Time complexity and asymptotic notations