Logarithm Time Complexity

The logarithm time complexity is present in many algorithms and it’s very effective. Therefore, it’s important to understand how it works so we can know how performant the algorithm that has this time complexity is.

In simple words, a logarithm is the number of times that a number multiplies itself to get a certain result. Let’s take a look at the mathematical function before seeing practical examples:

If we substitute b (base) with 2, then the result will be the x (exponential) number of 2 to result in x.

For example, in the context of algorithms let’s consider n = 16 and we have to figure out what is the power number that the base 2 should have for the result of 16.

log 2 ^ y = 16 == log 2 ^ 4 = 16

The number 2 powered by 4 is the same as 16. Therefore, the algorithm will have 4 iterations in its worst-case scenario.

Logarithm Time Complexity in Binary Search

Let’s take an example where we do the binary search algorithm which basically finds an element within a sorted array with 16 elements. You will see the O(log 16) in practice:

public class OLogNExample {

  // O (log(n)) time | O(1) space
  public static int binarySearch(int[] array, int target) {
    int middle = array.length / 2;

    var leftPointer = 0;
    var rightPointer = array.length - 1;

    int iterationsCount = 0;

    while (leftPointer <= rightPointer) {
      iterationsCount++;
      if (array[middle] < target) {
        leftPointer = middle + 1;
      } else if (array[middle] > target) {
        rightPointer = middle - 1;
      } else {
        System.out.println("Iterations count: " + iterationsCount);
        return middle;
      }

      middle = (leftPointer + rightPointer) / 2;
    }
    return -1;
  }

  @Test
  public void testCaseLog4() {
    int [] array = {2, 3, 5, 7, 8, 10, 13, 16, 17, 18, 19, 22, 25, 26, 28, 30};
    System.out.println(binarySearch(array, 2));
  }
}

Output:
Iterations count: 4
0

As you can see in the code above, it takes 4 iterations to find the number 2. If you do the calculation, you will find out that 2 ^ 4 = 16. Therefore, 4 iterations are the worst-case scenario to find element 2.

Another very important point is that the logarithm time complexity will be assumed to have the base 2 when dealing with algorithms. That’s because the algorithms we use the log(n) notation are the divide-and-conquer algorithms. This means that those algorithms will usually break an array in 2 many times or until the element is found or until the whole array is sorted in the case of sorting algorithms.

If we try to find the element that is exactly in the middle, the best-case scenario, then we will have only 1 iteration. If we test the above code by searching for 17 for example, this is the result:

@Test
  public void testCaseLog4() {
    int [] array = {2, 3, 5, 7, 8, 10, 13, 16, 17, 18, 19, 22, 25, 26, 28, 30};
    System.out.println(binarySearch(array, 2));
    System.out.println(binarySearch(array, 17));
  }

Output:
Iterations count: 1
8

If you want to learn more about the logarithm time complexity and Big(O) notation and how to measure the efficiency of an algorithm, you check out the Big(O) notation article.

Summary

The logarithm is a math function that in the context of algorithms the base will be assumed to be 2 because that’s what will happen the vast majority of times. Therefore, if we have a log(n) time complexity, this means that the time complexity will be how many times 2 will be multiplied by itself to get the result of n.

Let’s see the key points of logarithms in the context of algorithms:

• Logarithm is the number of times a number is multiplied by itself that results in the number n with the base of 2 in the context of algorithms. The log of 4 is 2 because 2 ^ 2 is 4.
• The number of iterations of an algorithm will be represented by the exponent number when the complexity is logarithmical.
• In the vast majority of the cases, the base for logarithms in algorithms’ time complexity will be 2. That’s because most algorithms that have logarithmic time complexity use the divide-and-conquer strategy, which means, it breaks the array in 2.
• A logarithmic time complexity might be faster than the exponent number in the best-case-scenario of that algorithm.