Introducing Big O notation
Introduction
Programmers write many algorithms. What they always should do is to ask themselves how 'good' an algorithm they have just written is. Big O notation is used to describe the performance of an algorithm and in particular, how it performs as the amount of data given to it increases, how well an algorithm scales. For example, how would an algorithm perform if it were given an array of 10 numbers to work with compared to an array with 100000 numbers in? Big O always looks for the worst case scenario. For example, if you had an algorithm that did a serial search through an array of 500 items, it would always assume that you find the item on the 500th search, or that the item didn't exist at all.
Performance is not the same as timing
Although you can measure how fast an algorithm goes using a program, it would be dependent on the hardware. For example, if an algorithm takes 0.0004 seconds to run on one machine, will it run faster on a computer with a faster processor? Timing an algorithm tells you about the computer hardware rather than the software. It is impossible to time an algorithm for all configurations of computers but what we can do is to evaluate the performance of an algorithm, and we can do this using Big O notation.
An example of Big O notation
Consider the following simplified equation as an example:
56n3 + 20n2 + 17
Using Big O notation, we can define the part of the equation that has the greatest effect on the answer.
If n = 1, the answer is 93 and all parts of the equation have an impact on the final answer.
If n = 2 (just one more value), then the answer is 321. The 17 at the end of the equation is actually not very significant. It doesn't really have much impact on the final answer.
If n = 10, the answer is 58017 and the 17 really is pretty insignificant now. Also, however, the 20n2 term is not that significant. It only contributed 2000 to the final answer.
In fact, the term that has the most impact on the final answer when n becomes large, is the 56n3 term. And even here, the term that has the most impact for larger numbers isn't the 56 part of the term but the n3 term.
We therefore say that this equation has an order of n cubed, and in Big O notation,
O(N3)
This is the idea behind Big O notation. We are using it to describe how well algorithms perform.