Click here to Skip to main content
12,446,146 members (81,374 online)
Click here to Skip to main content
Add your own
alternative version


3 bookmarked

Algorithm Time Complexity 1- What Is It

, 23 Jul 2015 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

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.


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.


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.

Growth of functions

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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

United Kingdom United Kingdom
No Biography provided

You may also be interested in...


Comments and Discussions

QuestionHalving the problem size Pin
jhog28-Jul-15 5:32
memberjhog28-Jul-15 5:32 
AnswerRe: Halving the problem size Pin
xszaboj28-Jul-15 5:47
memberxszaboj28-Jul-15 5:47 
GeneralRe: Halving the problem size Pin
jhog28-Jul-15 6:22
memberjhog28-Jul-15 6:22 
GeneralRe: Halving the problem size Pin
xszaboj28-Jul-15 8:30
memberxszaboj28-Jul-15 8:30 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160811.3 | Last Updated 24 Jul 2015
Article Copyright 2015 by xszaboj
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid