Big-O Notation - Determining Algorithm Efficiency

Big-O notation gives us the order of a function, a rough way of estimating algorithm efficiency, or at least comparing algorithms to see which is better. It is displayed in the form O(x), where x is the calculated efficiency. x is based on the amount of input used by the algorithm. For instance, a for loop executing N times is O(N).

The order can be found by looking at the dominating term, the term which grows the most. For instance, an operation that takes N^2 + 1 would be O(N^2), since the one becomes insignificant when N goes to infinite. These are the rules for dominance:
- Exponential functions of N dominate polynomial functions.
- Polynomial functions dominate logarithmic functions.
- Logarithmic functions dominate constants.
- A polynomial function dominates all other polynomial functions with a lower degree.

Other rules:
- Multiplication: O(N) x O(N) = O(N^2)
- Addition: O(N) + O(T) = O(greater of the two)