Logarithmic time complexity O(log n)

Logarithmic time complexity refers to the rate at which an algorithm runs with increasing input size logarithmically. Searching and sorting algorithms with logarithmic time complexity are most commonly used in divide-and-conquer algorithms. Binary search and quicksort are examples of such algorithms.

Example: Logarithmic Time O(log n)

The Binary Search algorithm searches an ordered set for an element. In order to solve a given problem, they break it down into similar subproblems. These subproblems are then recursively solved.

const binarySearchAlgo = (arr, num) => {
    let startIndex = 0;
    let endIndex = arr.length - 1;
    while (startIndex <= endIndex) {
      let midIndex = Math.floor((startIndex + endIndex) / 2);
  
      if (arr[midIndex] === num) {
        return midIndex;
      }
  
      if (arr[midIndex] > num) {
        endIndex = midIndex - 1;
      } else {
        startIndex = midIndex + 1;
      }
    }
    return -1;
  };
  
  let elements = [10, 20, 30, 40, 50, 60, 70];
  console.log(binarySearchAlgo(elements, 50)); 

Output

4

Explanation

Here lets find the position of number 50 using binary serach algorithm. To begin with, it checks the value at the center of the set.

The process is repeated on the left half of the set if the value of the element it is searching for is lower than the value of the one found. In case it's bigger, check the right half. As a result, the operation wont be performed on every element of data.

With every iteration, the input size decreases by half, making the time complexity O(log n).