The O() Notation

The O() notation is a mathematical way of dealing with approximations. When we write that a particular sort routine sorts n records in O(n²) time, we are simply saying that the worst-case time taken will vary as the square of n. Double the number of records, and the time will increase roughly fourfold. Think of the O as meaning on the order of. The O() notation puts an upper bound on the value of the thing we're measuring (time, memory, and so on). If we say a function takes O(n²) time, then we know that the upper bound of the time it takes will not grow faster than n². Sometimes we come up with fairly complex O() functions, but because the highest-order term will dominate the value as n increases, the convention is to remove all low-order terms, and not to bother showing any constant multiplying factors. O(n²/2+ 3n) is the same as O(n²/2), which is equivalent to O(n²). This is actually
a weakness of the O() notation—one O(n²) algorithm may be 1,000 times faster than another O(n²) algorithm, but you won't know it from the notation.
Figure 6.1 shows several common O() notations you'll come across, along with a graph comparing running times of algorithms in each category. Clearly, things quickly start getting out of hand once we get overO(n²).

Figure 1. Runtimes of various algorithms

For example, suppose you've got a routine that takes 1 s to process 100 records. How long will it take to process 1,000? If your code is O(1), then it will still take 1 s. If it's O(lg(n)), then you'll probably be waiting about 3 s. O(n) will show a linear increase to 10 s, while an O(n lg(n)) will take some 33 s. If you're unlucky enough to have an O(n²) routine, then sit back for 100 s while it does its stuff. And if you're using an exponential algorithm O(2ⁿ), you might want to make a cup of coffee—your routine should finish in about 10²⁶³ years. Let us know how the universe ends.
The O() notation doesn't apply just to time; you can use it to represent any other resources used by an algorithm. For example, it is often useful to be able to model memory consumption