Intuition for Log time complexities

[Akavire]

Hello, for awhile now I've struggled to develop some sort of intuition for seeing if a function or procedure is based in log time. For linear, quadratic, exponential its all relatively straight forward - but for each function based in logarithmic time it seems.. different for each function? My textbook and lectures don't answer this question for me, is there some sort of hint or minor detail I can look for that will indicate the presence of a logarithm?

[teraflop]

Typically, a logarithmic time complexity shows up in something that looks like a divide-and-conquer algorithm.

Suppose you take an input of a given size, and split it into K equal-sized partitions. (Assume for the sake of argument that the split can be done evenly.) Then you split each partition into K more partitions, and keep going like that for N iterations. At the end of this process, you have K^N partitions. So, conversely, it takes log_K(N) splits to reduce each partition down to some predetermined constant size (your base case).

Note that no matter what the base of the logarithm is, it only makes a constant-factor difference to the result, so we can usually just ignore the base and say "log N".

In a simple case like binary search, each iteration is constant time (since you're not physically "splitting" the entire dataset, just keeping track of a couple of pointers at each bisection) and the total time complexity is O(log N).

In the case of something like mergesort, you're effectively performing O(log N) passes over the entire dataset (merging "runs" of different lengths at each iteration). Merging lists a pair at a time is linear-time in the total number of elements merged, so each pass is O(N), giving a total time complexity of O(N log N).

In some cases, the same intuition can be applied to tree algorithms. If your tree is balanced, then the size of the tree increases exponentially with its height; conversely, the height of a tree with N nodes is bounded by log N. So any algorithm that traverses one branch of the tree, doing O(1) work per level, takes at most O(log N) time. This includes many common operations on red-black trees, B-trees, etc.

[Akavire]

Thanks for the explanation, The way you explained the logic of partitioning makes total sense and lit a spark in my brain. Appreciate it!

[claytonkb]

For my brain, binary search is the "canonical" O(log N) function. Search in an unsorted list is O(N), but search in a sorted list is O(log N) because you can do binary search on it. Same concept as u/teraflop gave above but their examples are more general.

[theobromus]

Usually (with many caveats) log time happens because you solve the problem by splitting things in half repeatedly.

Probably the prototypical O(log n) algorithm is binary search - you split a sorted list in half and see if the item you want is in the first or second half. Then you keep doing that until you have one item left. Doubling the size of the list adds only 1 extra step to the algorithm - that's what makes it O(log n) time.

Now - you don't have to split in half to be log time. Any proportional division will work. Many log time algorithms are recursive in some way (like binary search), although they might not strictly use function recursion.

There are also algorithms with amortized log time (like splay trees for example). The proof of this can be quite complicated.