notes blog about

O-notation

NOTE: Logarithms (log) mentioned here are base 2.

For example, simple search is O(n) algorithm and binary search is O(log n) algorithm. It means that if you have for example 100 (sorted) items you need to search through you need at most (worst-case scenario) 100 steps using simple search and 7 steps (guesses, operations) using binary search. Also notice that the growth rate of the binary search algorithm is much smaller.

n Simple search O(n) Binary search O(log n)
10 10 steps 4 steps
100 100 steps 7 steps
1 000 1 000 steps 10 steps

All this means that binary search is faster than simple search and it gets a lot faster as the input size increases.

Scaling

The following terms describe how a system performs as data size grows: the system is unaffected, gets bit slower, gets slower, or gets much slower.

O(1) - constant scaling

O(log n) - logarithmic scaling

image

O(n) - linear scaling

O(n^m) - exponential scaling

Resources