Data Structure and Algorithm
Complexity
Time Complexity

Understanding Time Complexity in JavaScript

Time complexity is the total time taken by an algorithm to run as a function of the length of the input. It's an important concept to evaluate the efficiency of algorithms.

Types of Time Complexities

Best Case (Ω, Omega)

The best-case scenario is the minimum time required for the algorithm to complete. It represents the lower bound of the algorithm.

Average Case (Θ, Theta)

The average case represents the expected time an algorithm would take to complete, considering all possible inputs.

Worst Case (O, Big O)

The worst-case scenario is the maximum time required for the algorithm to complete. It represents the upper bound of the algorithm.

Common Time Complexities

  • O(1): Constant time
  • O(log n): Logarithmic time
  • O(√n): Square root time
  • O(n): Linear time
  • O(n*m): Bilinear Time
  • O(log₂n): Logarithmic time
  • O(n log n): Linearithmic time
  • O(n²): Quadratic time
  • O(n³): Cubic time
  • O(2ⁿ): Exponential time

O(1): Constant Time

An algorithm with O(1) complexity takes the same amount of time regardless of the input size.

function printConstant(n) {
  for (let i = 1; i <= 10; i++) {
    console.log('Print');
  }
}

Explanation:

  • Input: None (the function runs a fixed number of times regardless of input size)
  • Operation: The loop runs a fixed 10 times
  • Reason for Time Complexity: Since the number of iterations is constant and does not depend on the input size, the time complexity is O(1). Here, the loop runs a fixed 10 times, no matter the input size n. Therefore, the time complexity is O(1).
function print(n) { // n input
  console.log('Hello'); // Single operation
}

Explanation:

  • Input: None (the function runs once regardless of input size)
  • Operation: A single console log operation
  • Reason for Time Complexity: This function has a single operation which runs once, regardless of the input size n. Thus, its time complexity is O(1).
console.log(n*(n+1)/2);

O(n): Linear Time

An algorithm with O(n) complexity grows directly with the input size.

function printNumber(n) {
  for (let i = 1; i <= n; i++) { // The loop runs n times
    console.log(i); // Operation inside loop
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The loop runs n times, printing each number from 1 to n
  • Reason for Time Complexity: The loop runs n times, and the time taken grows linearly with n. Hence, the time complexity is O(n). Here, the loop runs n times, and the time taken grows linearly with n. Hence, the time complexity is O(n).

O(n*m): Bilinear Time

An algorithm with O(n*m) complexity grows proportionally with the product of two inputs.

function printNM(n, m) {
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = 1; j <= m; j++) { // Inner loop runs m times for each iteration of the outer loop
      console.log(n, m); // Operation inside inner loop
    }
  }
}

Explanation:

  • Input: n and m (the sizes of the two inputs)
  • Operation: The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs m times.
  • Reason for Time Complexity: The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs m times. Therefore, the total number of operations is n _ m, resulting in O(n _ m) time complexity.

O(log n): Logarithmic Time

An algorithm with O(log n) complexity grows slowly as the input size increases.

function repeatedDivision(n) {
  while (n > 1) {
    n = Math.floor(n / 2); // The value of n is halved each iteration
    console.log(n); // Operation inside loop
  }
}
function repeatedLogarithmicPrint(n) {
  for (let i = 1; i <= n; i = i * 2) { // The value of i is doubled each iteration
    console.log('Print'); // Operation inside loop
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The loop starts with i initialized to 1, and in each iteration, i is multiplied by 2. This means that i takes the values 1, 2, 4, 8, 16, 32, ... until it exceeds n.
  • Reason for Time Complexity: The number of iterations is proportional to the logarithm of n (base 2). This is because each iteration effectively halves the problem size (in terms of the remaining values of i that need to be processed). Therefore, the time complexity is O(log₂n).

    In Big O notation, O(log n) and O(log₂n) essentially represent the same class of complexity.

for (let i = n; i >= 1; i = Math.floor(i / 2)) {
    console.log(i);
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The loop runs while n is greater than 1, halving n each time
  • Reason for Time Complexity: In each iteration, n is halved, so the number of iterations is logarithmic relative to n. Thus, the time complexity is O(log n). In this example, n is halved each time, so the number of iterations is logarithmic relative to n. Thus, the time complexity is O(log n).
function printSquareRoot(n) {
  while (n > 1) {
    n = Math.sqrt(n); // The value of n is updated to its square root
    console.log(n); // Print the updated value of n
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The function repeatedly updates n to its square root and prints it
  • Reason for Time Complexity: In each iteration, n is replaced with its square root. The number of iterations required to reduce n to a value less than or equal to 1 grows logarithmically with respect to n. Hence, the time complexity is O(log₂(log₂n)), but it’s often simplified to O(log n) in discussions.

O(√n): Square Root Time

An algorithm with O(√n) complexity grows with the square root of the input size.

function printFactors(n) {
  for (let i = 1; i * i <= n; i++) { // Loop runs approximately √n times
    if (n % i === 0) { // Check if i is a factor of n
      console.log(i); // Print factor
      if (i !== n / i) { // Print complementary factor
        console.log(n / i);
      }
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The loop runs from 1 to the square root of n, checking if i is a factor of n and printing it
  • Reason for Time Complexity: The loop runs approximately √n times because i goes up to the square root of n. Hence, the time complexity is O(√n).

O(log₂n): Logarithmic Time

Logarithmic time complexity, O(log₂n), describes an algorithm that reduces the problem size by a constant fraction each step. This type of complexity is typical for algorithms that divide the input in half every time.

function binarySearch(arr, target) {
    let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
      let mid = Math.floor((left + right) / 2);
 
    if (arr[mid] === target) {
        return mid; // Target found
    } else if (arr[mid] < target) {
        left = mid + 1; // Search in the right half
    } else {
        right = mid - 1; // Search in the left half
    }
  }
 
  return -1; // Target not found
}

Explanation:

  • Input: arr (the array to search), target (the value to search for)
  • Operation: The loop divides the search interval in half each time, checking if the target is in the left or right half
  • Reason for Time Complexity: Binary search reduces the problem size by half in each iteration. Therefore, the time complexity is O(log₂n). Binary search is a classic example of an algorithm with O(log₂n) complexity. It works by repeatedly dividing the search interval in half.

O(n log n): Linearithmic Time

An algorithm with O(n log n) complexity is a bit more than linear but not too much.

function sumAllPairsLogStep(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = i; j <= n; j *= 2) { // Inner loop runs log(n) times
      sum += i * j; // Operation inside inner loop
    }
  }
  return sum;
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times and the inner loop runs log(n) times for each iteration of the outer loop
  • Reason for Time Complexity: The outer loop runs n times and the inner loop runs log(n) times for each iteration of the outer loop. Therefore, the time complexity is O(n log n). The outer loop runs n times and the inner loop runs log(n) times for each iteration of the outer loop. Therefore, the time complexity is O(n log n).

O(n²): Quadratic Time

An algorithm with O(n²) complexity grows much faster than the input size.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) { // Outer loop runs n times
    for (let j = 0; j < arr.length - i - 1; j++) { // Inner loop runs n times for each outer loop iteration
      if (arr[j] > arr[j + 1]) { // Compare adjacent elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // Swap if out of order
      }
    }
  }
  return arr;
}

Explanation:

  • Input: arr (the array to sort)
  • Operation: The outer loop runs n times, and the inner loop runs (n-i-1) times for each iteration of the outer loop, performing comparisons and swaps if necessary.
  • Reason for Time Complexity: The outer loop runs n times and the inner loop runs n times for each iteration of the outer loop, resulting in O(n²) time complexity.
function printPattern(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i * 2; j++) { // Inner loop runs 2*i times for each iteration of the outer loop
      console.log('Print');
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, and the inner loop runs 2*i times for each iteration of the outer loop
  • Reason for Time Complexity: The number of operations performed by the inner loop grows linearly with i for each iteration of the outer loop. Summing up these operations over all iterations of the outer loop results in a quadratic growth with respect to n. Hence, the time complexity is O(n²).

O(n² √n): Quadratic Square Root Time

An algorithm with O(n² √n) complexity grows with the square of the input size, multiplied by the square root of the input size.

function tripleNestedLoopSquareRootStep(n) { // n input
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = 1; j <= n; j++) { // Middle loop runs n times
      for (let k = 1; k * k <= n; k++) { // Inner loop runs approximately √n times
        console.log(i, j, k);
      }
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop and middle loop each run n times, while the inner loop runs approximately √n times
  • Reason for Time Complexity: The outer and middle loops each run n times, and the inner loop runs approximately √n times. Therefore, the time complexity is O(n² √n).

O(n³): Cubic Time

An algorithm with O(n³) complexity grows even faster than quadratic time.

function printComplexPatterns(n) {
  for (let i = 1; i <= n; i++) { // Outer loop: runs n times
    for (let j = 1; j <= i * 2; j++) { // Middle loop: runs i * 2 times
      for (let k = 1; k <= n / 2; k++) { // Inner loop: runs n / 2 times
        console.log('Print');
      }
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times. For each iteration of the outer loop, the middle loop runs up to 2 * i times (which sums to O(n²) over all iterations). The inner loop runs n / 2 times for each iteration of the middle loop (simplified to O(n)).
  • Reason for Time Complexity: The outer loop runs n times, the middle loop runs O(n²) times in total, and the inner loop runs O(n) times for each iteration of the middle loop. Thus, the overall time complexity is O(n³).
function tripleNestedLoop(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      for (let k = 1; k <= n; k++) {
        console.log(i, j, k);
      }
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, the middle loop runs n times for each iteration of the outer loop, and the inner loop runs n times for each iteration of the middle loop.
  • Reason for Time Complexity: The outer loop runs n times, the middle loop runs n times for each iteration of the outer loop, and the inner loop runs n times for each iteration of the middle loop. Therefore, the time complexity is O(n³).
function printNestedLoops(n) { // Input: `n`
  for (let i = 1; i <= n; i++) {  // Outer loop: Runs `n` times, iterating over each value from 1 to `n`.
    for (let j = 1; j <= i * i; j++) {   // Inner loop: For each value of `i`, runs `i * i` times (i.e., `i` squared).
      console.log('Print');
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs i² times, where i is the current value of the outer loop variable
  • Reason for Time Complexity: The inner loop runs up to i² times for each iteration of the outer loop, resulting in a total time complexity of O(n³), since the total number of operations is proportional to the sum of squares from 1 to n.
function sumPairsWithLogLoop(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = 1; j <= n; j++) { // Middle loop runs n times for each outer loop iteration
      for (let k = j; k <= n; k *= 2) { // Inner loop runs log(n) times for each middle loop iteration
        sum += i + j + k; // Accumulate the sum of i, j, and k
      }
    }
  }
  return sum;
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, the middle loop runs n times for each iteration of the outer loop, and the inner loop runs approximately log(n) times for each iteration of the middle loop (due to the multiplication by 2).
  • Reason for Time Complexity: The outer and middle loops each run n times, leading to a cubic time complexity. The inner loop runs log(n) times, which affects the multiplicative constant, but the dominant term remains O(n³).
function printAllPairs(n) {
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = 1; j <= n; j++) { // Inner loop runs n times for each outer loop iteration
      console.log(i, j); // Print pair (i, j)
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, and for each iteration of the outer loop, the inner loop also runs n times.
  • Reason for Time Complexity: The outer loop and the inner loop each run n times, resulting in n * n operations. Thus, the time complexity is O(n²). In this example, the outer loop runs n times and the inner loop runs n times for each iteration of the outer loop, leading to O(n³) time complexity.

O(n √n): Square Root Linear Time

An algorithm with O(n √n) complexity grows with the square root of the input size, multiplied by the linear factor.

function printPairsSquareRootStep(n) {
  for (let i = 1; i <= n; i++) { // Outer loop runs n times
    for (let j = 1; j * j <= n; j++) { // Inner loop runs approximately √n times
      console.log(i, j); // Operation inside inner loop
    }
  }
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The outer loop runs n times, and the inner loop runs while j * j is less than or equal to n, which is approximately √n times.
  • Reason for Time Complexity: The inner loop runs approximately √n times for each iteration of the outer loop. Therefore, the overall time complexity is O(n √n).

O(2ⁿ): Exponential Time

An algorithm with O(2ⁿ) complexity grows extremely quickly.

function fibonacci(n) {
  if (n <= 1) { // Base case
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Recursive calls
}

Explanation:

  • Input: n (the size of the input)
  • Operation: The function calls itself twice for each value of n, resulting in an exponential number of calls
  • Reason for Time Complexity: The function makes two recursive calls for each value of n, resulting in an exponential growth of function calls. Hence, the time complexity is O(2ⁿ). In this example, each call to fibonacci results in two more calls, leading to an exponential growth of function calls. Hence, the time complexity is O(2ⁿ).

Conclusion

Understanding time complexity helps in evaluating and optimizing the performance of algorithms. By analyzing the complexity of our code, we can make better decisions and write more efficient programs. The examples above illustrate how different algorithms perform as the input size grows, helping us choose the best approach for our needs.

Happy coding! 😊

DSA With JavaScriptSpace Complexity