33

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

gnat
  • 21,442
  • 29
  • 112
  • 288
Atif
  • 915
  • 1
  • 6
  • 12
  • 2
    http://stackoverflow.com/questions/749819/how-to-know-when-big-o-is-logarithmic or this really lengthy read: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – wkl Apr 26 '12 at 00:55
  • Ah, that's the one place I didn't look :) – Atif Apr 27 '12 at 14:58

5 Answers5

44

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.

Caleb
  • 38,959
  • 8
  • 94
  • 152
  • 4
    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". –  Apr 26 '12 at 08:09
  • @Caleb the actual base of the logarithm is unimportant when talking scaling. –  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. –  Apr 26 '12 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. –  Apr 26 '12 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. – Caleb Apr 26 '12 at 23:38
30

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.

Community
  • 1
Casey Patton
  • 5,211
  • 7
  • 33
  • 41
  • 1
    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
  • 1
    @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
  • 2
    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
  • Yes, it's much better now, but still, I don't like this approach. Your answer presents a rule-of-thumb in an area where you don't need such thing. Asymptotic complexity is well-defined, there is no need for such "rules", only a clear understanding of the definition. – Tamás Szelei Apr 27 '12 at 10:23
  • To each his own! I think a rule of thumb for newcomers is a nice way to get the general idea before diving into a formal definition. But that's just my opinion, and you're welcome to yours. – Casey Patton Apr 27 '12 at 17:27
5

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.

Kris Harper
  • 2,237
  • 2
  • 19
  • 21
1

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.

scarfridge
  • 1,796
  • 13
  • 20
0

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

Pieter B
  • 12,867
  • 1
  • 40
  • 65