# Determining if an Algorithm is O (log n)

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.

• Note that a more colloquial way to say "on the order of the logarithm of the size" is to say "on the order of the number of digits in the size".
– user1249
Apr 26, 2012 at 8:09
• @Caleb the actual base of the logarithm is unimportant when talking scaling.
– user1249
Apr 26, 2012 at 21:46
• @Caleb talking absolutes does not make sense with big-O. A wording you might like better: when the number of digits double, the number of steps double.
– user1249
Apr 26, 2012 at 22:47
• @Caleb talking absolutes does not make sense with big-O. A wording you might like better: when the number of digits double, the number of steps double.
– user1249
Apr 26, 2012 at 23:29
• @ThorbjørnRavnAndersen Yes, that's what "the logarithm of the size" means. I'm not sure what your problem with the phrase is, except that you'd have chosen to say it differently. Fundamentally, I think we agree. Apr 26, 2012 at 23:38

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.

• What if I split the input in two and then iterate 2^(n/2) times on the remainder before splitting it again? (Of course I know what then, I just wanted to show an example where this simplistic approach fails). Apr 26, 2012 at 10:29
• @afish That's kind of rare. It's spectacularly rare when searching. Apr 26, 2012 at 10:53
• @DonalFellows Algorithm theory is not an empirical science. And the question was not about searching, it's just that the mention of `log n` triggered binary search reflexes in people. Apr 26, 2012 at 13:08
• Partitioning doesn't make the algorithm O(log n), it (usually) adds a factor of log n to the big-O limit. Recursive sorts like heapsort and mergesort are perfect examples: they partition the input, but then they recursively partition both the resulting partitions. The result is O(n log n) performance. Apr 26, 2012 at 14:33
• @afish: Good point. My goal with this answer is to keep it as simple as possible given the nature of the question. I changed the line "you divide the structure in half..." to "you divide the structure in half...and do a constant number of operations for each split" to try to get this point across simply. Apr 26, 2012 at 23:54

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.

• So, what is wrong with my answer? I'm open to constructive criticism. Apr 26, 2012 at 10:36

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).

• Everyone should give this answer one upvote and one downvote, both for obvious reasons :-) Aug 24, 2015 at 21:37