How to know when Big O is Logarithmic?

Question

My question arises from the post "Plain English Explanation of Big O". I don't know the exact meaning for logarithmic complexity. I know that I can make a regression between the time and the number of operations and calculate the X-squared value, and determine so the complexity. However, I want to know a method to determine it quickly on paper.

How do you determine logarithmic complexity? Are there some good benchmarks?

Answer 1

Not sure if this is what you mean, but... logarithmic complexity usually arises when you're working with a spread-out data structure like a balanced binary tree, which contains 1 node at the root, 2 children, 4 grandchildren, 8 great-grandchildren, etc. Basically at each level the number of nodes gets multiplied by some factor (2) but still only one of those is involved in the iteration. Or as another example, a loop in which the index doubles at each step:

for (int i = 1; i < N; i *= 2) { ... }

Things like that are the signatures of logarithmic complexity.

Answer 2

Not rigorous, but it you have an algorithm that is essentially dividing the work needed to be done by half on each iteration, then you have logarithmic complexity. The classic example is binary search.

Answer 3

Master theorem usually works.

Answer 4

If you just want to know about logarithmic Big Oh, be on the lookout for when your data is cut in half each step of the recurrence.

This is because if you are processing data that is 1/2 as big as the step before it, it is an infinite series.

Answer 5

Here is another way of saying it.

Suppose your algorithm is linear in the number of digits in the size of the problem. So, perhaps you have a new algorithm to factor a large number, that you can show to be linear in the number of digits. A 20 digit number thereby takes twice as long to factor as a 10 digit number using your algorithm. This would have log complexity. (And it would be worth something for the inventor.)

Bisection has the same behavior. It takes roughly 10 bisection steps to cut the interval length by a factor of 1024 = 2^10, but only 20 steps will cut the interval by a factor of 2^20.

Log complexity does not always mean an algorithm is fast on all problems. The linear factor in front of the O(log(n)) may be large. So your algorithm may be terrible on small problems, not becoming useful until the problem size is appreciably large that other algorithms die an exponential (or polynomial) death.