How to know which function has complexity of log n

Question

I was learning about the time complexities and was stuck at Big O(log n) bcoz I was unable to identify which function has the complexity of log n as compared to other complexities such as O(n), O(n2) or O(n3) which can be easily identified by counting the number of for loops in the fucntion

Answer 1

You want to look at two things:

• How many times does the loop iterate? (depth)
• How much of the array does it access during each iteration? (breadth)

For the depth:

• If each iteration divides the number of remaining iterations by some amount (often 2), there are probably log(n) iterations, so the depth is O(log(n)). The exact value it's divided by doesn't matter for big O, since log_2(n), log_e(n), log_10(n), etc. are all constant multiples of each other.
• If it iterates a fixed number of times, it's O(1).
• If it iterates n times (or a constant multiple of that), it's O(n)

For the breadth, ask how many elements of the original array it needs to look at each iteration.

• If that number doesn't depend on the size at all, breadth is O(1) (e.g. in a binary search, we only look at a single element each iteration, regardless of the array size).
• If you look at the entire array, or some constant fraction of it, e.g. n/2, the breadth is O(n). This is often the case for the good sorting algorithms. (These generally work by recursion rather than looping, which means the depth is depth of recursion rather than number of iterations. For these, you ask how much of the array is accessed collectively by all recursive calls at the same layer. If you haven't learned recursion yet, feel free to ignore this parenthetical for now.)

Once you have the big O estimates of breadth and depth, just multiply them together.

• Binary search of a sorted array has depth log(n) and breadth O(1), so it's O(log(n))
• Merge sort has depth O(log(n)) and breadth O(n), so it's O(n log(n))
• Adding all the numbers in an array has depth O(n) and breadth O(1), so it's O(n).
• Adding two numbers has depth O(1) and breadth O(1), so it's O(1).

There are complications in practice, of course (usually for the recursive cases), but these heuristics will get you started. A technique that might be useful for the more complicated cases is sketching out the elements that are accessed by each iteration/recursive call. Depth vertically, breadth horizontally. As long as you don't have multiple function calls accessing the same memory in the same row, you can usually see what's happening well enough to add things up.