Why not use seconds to evaluate algorithm's effectiveness?

Answer 1

An algorithm cannot be measured in seconds because:

* timing will be different on different machines * timing will be different on the same machine in a different configuration * when an algorithm takes n seconds to complete, that only holds true for one set of input

The biggest problem up there is that timing an algorithm only gives us information about one output for a specific input. What we really want to know is how well the algorithm will scalewith input. If you double the number of values you send as input will your algorithm take twice as long? Four times? Will it not scale linearly?

In computer science we use what is known as "Big O notation" to describe how well an algorithm scales. Let's look at some common examples:

Linear search can be represented in Big O as O(n). This is because the algorithm searches through each element in your list one at a time until it finds the target value. For a list of any size n, it will make n comparisons.

Selection sort can be represented as O(n2) for the same reason. For a list of size n, each element will need to be compared to each other element, giving us n*n comparisons.

More complex algorithms have more difficult evaluations.

A binary search algorithm will cut the amount of data it needs to search in half on each iteration. This gives us O(log n).