I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it?
I know with O(n), you usually have a single loop; O(n^2) is a double loop; O(n^3) is a triple loop, etc. How about O (log n)?
I know with O(n), you usually have a single loop; O(n^2) is a double loop; O(n^3) is a triple loop, etc. How about O (log n)?
You're really going about it the wrong way here. You're trying to memorize which big-O expression goes with a given algorithmic structure, but you should really just count up the number of operations that the algorithm requires and compare that to the size of the input. An algorithm that loops over its entire input has O(n) performance because it runs the loop n times, not because it has a single loop. Here's a single loop with O(log n) performance:
for (i = 0; i < log2(input.count); i++) {
doSomething(...);
}
So, any algorithm where the number of required operations is on the order of the logarithm of the size of the input is O(log n). The important thing that big-O analysis tells you is how the execution time of an algorithm changes relative to the size of the input: if you double the size of the input, does the algorithm take 1 more step (O(log n)), twice as many steps (O(n)), four times as many steps (O(n^2)), etc.
Does it help to know from experience that algorithms that repeatedly partition their input typically have 'log n' as a component of their performance? Sure. But don't look for the partitioning and jump to the conclusion that the algorithm's performance is O(log n) -- it might be something like O(n log n), which is quite different.
The idea is that an algorithm is O(log n) if instead of scrolling through a structure 1 by 1, you divide the structure in half over and over again and do a constant number of operations for each split. Search algorithms where the answer space keeps getting split are O(log n). An example of this is binary search, where you keep splitting an ordered array in half over and over again until you find the number.
Note: You don't necessarily need to be splitting in even halves.
log n triggered binary search reflexes in people.
Commented
Apr 26, 2012 at 13:08
The typical examples are ones that deal with binary search. For example, a binary search algorithm is usually O(log n).
If you have a binary search tree, lookup, insert and delete are all O(log n) complexity.
Any situation where you continually partition the space will often involve a log n component. This is why many sorting algorithms have O(nlog n) complexity, because they often partition a set and sort as they go.
If you want it as simple as "single loop -> O(n), double loop -> O(n^2)", than the answer is probably "Tree -> O(log n)". More accurately traversing a tree from root to one (not all!) leaf or the other way round. However, these are all oversimplifications.
You want to know if there is an easy way to identify if an algorithm is O(log N).
Well: just run and time it. Run it for inputs 1.000, 10.000, 100.000 and a million.
If you see like a running time of 3,4,5,6 seconds (or some multiple) you can safely say it's O(log N). If it's more like : 1,10,100,1000 seconds then it's probably O(N). And if it's like 3,40,500,6000 seconds then it's O(N log N).
