Time Complexity

<aside> 💡

Time Complexity: It is used to measure efficiency of algorithm, in terms of speed, as the input size grows.

</aside>

Time complexity **≠** time taken by algorithm

Binary search efficency >>>> Linear search efficency

To represent time complexity we use Big O Notation.

Big O notation (O): A mathematical notation used to classify the efficiency of algorithms based on how their runtime grows with input size.

We measure it in the worst case.

<aside> 💡

Linear Search time complexity ⇒ O(n)

Binary Search time complexity ⇒ O(log n)

</aside>

Types of Big O Notations

• Constant Complexity O(1): When your algorithm is not dependent on the input size n, it is said to have a constant time complexity with order O(1). This means that the run time will always be the same regardless of the input size. For example, if an algorithm is to return the first element of an array. Even if the array has 1 million elements, the time complexity will be constant if you use this approach:

  const firstElement = (array) => {
    return array[0];
  };
  
  let arr = [12, 55, 67, 94, 22];
  console.log(firstElement(arr)); // 12
  
  

• Linear Time O(n): You get linear time complexity when the running time of an algorithm increases linearly with the size of the input. This means that when a function has an iteration that iterates over an input size of n, it is said to have a time complexity of order O(n). For example, if an algorithm is to print all even numbers from an array, iterate over an array for each element means length of the array times the loop will run.

  let arr = [10, 3, 5, 2, 7, 6, 9];
  for (let i = 0; i < arr.length; i++) {
      if (arr[i] % 2 === 0) {
          console.log(arr[i]);
      }
  } // 10, 2, 6
  

• Logarithm Time O(log n): When the input size decreases on each iteration or step, an algorithm is said to have logarithmic time complexity. When the input size is reduced by half, maybe when iterating, handling recursion, or whatsoever, it is a logarithmic time complexity (O(log n)). A great example is binary search functions, which divide your sorted array based on the target value. For example, an algorithm for count number of digits of an integer, then time complexity will be O(log₁₀(n)).

  function countDigits(n) {
    if (n === 0) return 1;
    n = Math.abs(n);
    let count = 0;
    while (n > 0) {
      n = Math.floor(n / 10);
      count++;
    }
    return count;
  }
  
  console.log(countDigits(259)); // 3
  

• Loglinear Time O(n log n): If you have a loop that runs n times and within that loop, you perform a logarithmic operation, the complexity is O(n log n). O(n log n) time complexity is generally seen in sorting algorithms like Quick Sort, Merge Sort, Heap Sort.

• Quadratic Time O(n^2): When you perform nested iteration, meaning having a loop in a loop, the time complexity is quadratic, which is horrible. A perfect way to explain this would be if you have an array with n items. The outer loop will run n times, and the inner loop will run n times for each iteration of the outer loop, which will give total n^2 prints.

  const matchElements = (array) => {
    for (let i = 0; i < array.length; i++) {
      for (let j = 0; j < array.length; j++) {
        if (i !== j && array[i] === array[j]) {
          return `Match found at ${i} and ${j}`;
        }
      }
    }
    return "No matches found 😞";
  };
  
  const fruit = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];
  console.log(matchElements(fruit)); // "Match found at 2 and 8"