11,932,677 members (59,322 online)
Technical Blog
alternative version

3.2K views
3 bookmarked
Posted

Algorithm Time Complexity 1- What Is It

, 23 Jul 2015 CPOL
 Rate this:
What is Algorithm Time Complexity?

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.

```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.

Share

 United Kingdom
No Biography provided

You may also be interested in...

 First Prev Next
 Halving the problem size jhog28-Jul-15 6:32 jhog 28-Jul-15 6:32
 Re: Halving the problem size xszaboj28-Jul-15 6:47 xszaboj 28-Jul-15 6:47
 Re: Halving the problem size jhog28-Jul-15 7:22 jhog 28-Jul-15 7:22
 Re: Halving the problem size xszaboj28-Jul-15 9:30 xszaboj 28-Jul-15 9:30
 Last Visit: 31-Dec-99 19:00     Last Update: 30-Nov-15 12:45 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.