Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
2… or this really lengthy read:… – birryree Apr 26 '12 at 0:55
Ah, that's the one place I didn't look :) – Atif Apr 27 '12 at 14:58
up vote 19 down vote accepted

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++) {

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.

share|improve this answer
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 '12 at 8:09
+1, for mentioning the meaning of big-O. – NoChance Apr 26 '12 at 8:31
@Caleb the actual base of the logarithm is unimportant when talking scaling. – user1249 Apr 26 '12 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 '12 at 22:47
Thanks, Caleb. Your code snippet really helped – Atif Apr 27 '12 at 15:00

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.

share|improve this answer
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). – Tamás Szelei Apr 26 '12 at 10:29
@afish That's kind of rare. It's spectacularly rare when searching. – Donal Fellows Apr 26 '12 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. – Tamás Szelei Apr 26 '12 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. – Caleb Apr 26 '12 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. – Casey Patton Apr 26 '12 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.

share|improve this answer

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.

share|improve this answer
So, what is wrong with my answer? I'm open to constructive criticism. – scarfridge Apr 26 '12 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).

share|improve this answer
Everyone should give this answer one upvote and one downvote, both for obvious reasons :-) – gnasher729 Aug 24 '15 at 21:37

protected by gnat Aug 24 '15 at 11:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.