Hands-On Data Structures and Algorithms with JavaScript

Logarithmic time

A Logarithmic time function is one in which the time of execution is proportional to the logarithm of the input size. Consider the following example:

for(var i = 1; i < N; i *= 2) {    // O(1) operations}

We can see that in any given iteration, the value of i = 2ⁱ, so in the n^th iteration, the value of i = 2ⁿ. Also, we know that the value of i is always less than the size of the loop itself (N). From that, we can deduce the following result:

2n < Nlog(2n) < log(N)n < log(N) 

From the preceding code, we can see that the number of iterations would always be less than the log on the input size. Hence, the worst-case time complexity of such an algorithm would be O(log(n)).

Let's consider another example, where we halve the value ...