Time Complexity of Algorithms

If you are a web developer or a programmer in general, you have most likely written algorithms for various tasks. Examples are: searching through a table, sorting an array of numbers by descending value, calculating the shortest path to get to a location… But what qualifies an algorithm to be a good algorithm?

One specification of an algorithm is its correctness. You will probably assume that your algorithm works after testing it out a few times. However, if you can mathematically prove that your algorithm will work as expected for every input value possible, this is a huge bonus. I will not go further in to that subject in this writing.

Another specification is its efficiency: how does the computing time relate to the amount of input? Is it a linear relation? Does computing time rise exponentially for the doubling of input? That’s what this article will be about.

Time Complexity

Time complexity is, as mentioned above, the relation of computing time and the amount of input. This is usually about the size of an array or an object. Time complexity also isn’t useful for simple functions like fetching usernames from a database, concatenating strings or encrypting passwords. It is used more for sorting functions, recursive calculations and things which generally take more computing time.

This is not because we don’t care about that function’s execution time, but because the difference is negligible. We don’t care if it takes 10ms instead of 3ms to fetch a username. However, if we have a recursive sorting algorithm which takes 400ms and we can reduce that to 50ms, that would be an interesting thing to do.

As you might guess, the lower the computing time, the more efficient the algorithm is. The question that follows is: ‘how can we define time complexity in an universal way?’. That’s where we’ll use the ‘Big O notation’.

Big O notation

The Big O notation is a notation for the time complexity of an algorithm. It is a mathematical representation of the upper bound of the limit of the scaling factor of the algorithm. For example, if we double the size of an input array, by how much does the computing time increase? This might become clear with two examples:

$numbers = array(14,82,4,0,24,28);
foreach($numbers as $number)
{
    echo $number;
} 

Continue reading %Time Complexity of Algorithms%

more