Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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  
stackoverflow.com/questions/749819/… or this really lengthy read: stackoverflow.com/questions/487258/… –  birryree Apr 26 '12 at 0:55
    
Ah, that's the one place I didn't look :) –  Atif Apr 27 '12 at 14:58

5 Answers 5

up vote 15 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++) {
    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.

share|improve this answer
3  
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  
+1, for mentioning the meaning of big-O. –  Emmad Kareem 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
1  
Thanks, Caleb. Your code snippet really helped –  Atif Apr 27 '12 at 15:00

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

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

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

Divide and conquer algorithms usually have a log n component to the running time. This comes from the repeated halving of the input.

In the case of binary search, every iteration you throw away half of the input. It should be noted that in Big-O notation, log is log base 2

share|improve this answer
    
The convention that log is the binary logarithm is a computer science convention. Big O notation comes from math esp. analysis and there log will not refer to log2. (I did not downvote your answer.) –  scarfridge Apr 26 '12 at 11:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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