Data Structures and Algorithms in JavaScript: BigO

How to Analyze Time Complexity of Algorithms.

• Consider the worst-case scenario for time complexity analysis.
• Focus on the dominant term when expressing time complexity using Big O notation.
• Analyze loops, recursive calls, and nested structures carefully.

O(1) — Constant Time:

Operations take a constant amount of time, regardless of the input size.

function exampleConstantTimeAlgorithm(arr) {
    return arr[0]
}

O(log n) — Logarithmic Time:

The algorithm’s runtime grows logarithmically with the input size.

In this case, the loop doubles the value of i with each iteration. This behavior results in a logarithmic number of iterations, and the time complexity is O(log n). Binary Search is another example.

function exampleLogarithmicTimeAlgorithm(n) {
    let i = 1
    while (i < n) {
        i *= 2
    }
    return i
}

function binarySearch(sortedArray, target) {
  let low = 0
  let high = sortedArray.length - 1

  while (low <= high) {
    let mid = Math.floor((low + high) / 2)

    if (sortedArray[mid] === target) {
      return mid // Found the target element
    } else if (sortedArray[mid] < target) {
      low = mid + 1 // Search the right half
    } else {
      high = mid - 1 // Search the left half
    }
  }

  return -1 // Target element not found
}

O(n) — Linear Time:

The runtime is directly proportional to the input size.

function exampleLinearTimeAlgorithm(arr) {
    for (let i = 0; i < arr.length; i++) {
        // some operation
    }
}

O(n²) — Quadratic Time:

The runtime grows quadratically with the input size.

function exampleQuadraticTimeAlgorithm(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            // some operation
        }
    }
}

O(2^n) — Exponential Time:

Grows very quickly with even small increases in the input size.

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2)
  }
}

// Example usage
console.log(fibonacci(7)) // Output: 13

Common Cases:

1. Array

• Insert at End: O(1) Constant.
• Insert at Beginning: O(n) Linear.
• Insert in the Middle: O(n) Linear.
• Remove from End: O(1) Constant.
• Remove from Beginning: O(n) Linear.
• Remove in the Middle: O(n) Linear.
• Find value: O(n) Linear.
• Access value: O(1) Constant.

2. Linked List

• Insert at End: O(1) Constant with the tail pointer (Doubly Linked List), O(n) Linear if use traverse.
• Insert at Beginning: O(1) Constant.
• Insert in the Middle: O(1) Constant with direct access to the node, O(n) Linear if use traverse.
• Remove from End: O(1) Constant if have the tail pointer (Doubly Linked List), O(n) Linear if use traverse.
• Remove from Beginning: O(1) Constant.
• Remove in the Middle: O(1) Constant with direct access to the node, O(n) Linear if use traverse.
• Find value: O(n) Linear.
• Access value: O(n) Linear.

3. Stack

• Insert at End: O(1) Constant.
• Insert at Beginning: N/A (not available).
• Remove from End: O(1) Constant.
• Remove from Beginning: N/A (not available).
• Find value: O(n) Linear.
• Access value: O(n) Linear.

4. Queue

• Insert at End: N/A (not available).
• Insert at Beginning: O(1) Constant.
• Remove from End: O(1) Constant.
• Remove from Beginning: N/A (not available).
• Find value: O(n) Linear.
• Access value: O(n) Linear.

5. Tree

• Insert: O(1) Constant if the element is known, O(n) Linear if use traverse.
• Remove: O(1) Constant if the element is known, O(n) Linear if use traverse.
• Traverse: O(n) Linear.