Re:What does O(log n) mean, exactly?
by jgross206 on Sunday May 26, 2013 @12:59PM
(#5771606)
Not sure of the universality of this, but my intuitive way of understanding O(log n) is as follows:
An algorithm is O(log n) if you can reduce the solution space (the set of all possible solutions) by a fraction (e.g. divide it in half or divide it into tenths) using a constant number of operations.
For example, binary search is O(log n) because you can cut the solution space in half (regardless of how big it is) by using a constant number of operations.
An algorithm is O(log n) if you can reduce the solution space (the set of all possible solutions) by a fraction (e.g. divide it in half or divide it into tenths) using a constant number of operations.
For example, binary search is O(log n) because you can cut the solution space in half (regardless of how big it is) by using a constant number of operations.