base of logarithms in time-complexity algorithms

In Computer Science, it’s often base 2. This is because many divide and conquer algorithms that exhibit this kind of complexity are dividing the problem in two at each step.

Binary search is a classic example. At each step, we divide the array into two and only recursively search in one of the halves, until you reach a base case of a subarray of one element (or zero elements). When dividing an array of length n in two, the total number of divisions before reaching a one element array is log2(n).

This is often simplified because the logarithms of different bases are effectively equivalent when discussing algorithm analysis.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)