📐

Understanding Time Complexity of OLog(N): Math + Intuition

For most binary search problems, we reduce the array size by half at each iteration. To find the time complexity, we can ask how many times we will have to divide our original array of size (n) until we reach 1.

$n * \frac{1}{2}* \frac{1}{2}* \frac{1}{2}* \frac{1}{2}* \frac{1}{2}... = 1$

$n * (\frac{1}{2})^x = 1$ (x = how many times)

$n * (\frac{1^x}{2^x}) = 1$

$n * (\frac{1}{2^x}) = 1$

$(\frac{n}{2^x}) = 1$

$n = 2^x$

How to Separate x out of the exponent. Logarithms? Take log base 2 on both sides

$\log_{2} n = \log_{2} 2^x$

What power must we raise 2 to get 2^x , that is just x

$\log_{2} n = x$

We need to half the array log n times to get to 1. So that’s how many times we need to make iterations on an array of size n.

Time Complexity: O(log(n))

💡

Reference(Time complexity)

💡

Reference(Logarithms)