Binary Search vs Linear Search Real Cost Difference in DSA Javascript - Complexity Comparison

Time Complexity: Binary Search vs Linear Search Real Cost Difference

O(n) for Linear Search, O(log n) for Binary Search

Understanding Time Complexity

We want to understand how searching for a value in a list changes as the list grows.

Which search method works faster when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of these two search methods.

// Linear Search
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Binary Search (array must be sorted)
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
    

Linear search checks each item one by one. Binary search splits the list in half repeatedly to find the target.

Identify Repeating Operations

Look at what repeats in each method.

• Linear Search primary operation: Checking each element one by one in a loop.
• Linear Search how many times: Up to n times, where n is the list size.
• Binary Search primary operation: Comparing the middle element and cutting the search space in half.
• Binary Search how many times: About log₂ n times, because the list halves each step.

How Execution Grows With Input

How many checks happen as the list grows?

Input Size (n)	Linear Search Checks	Binary Search Checks
10	Up to 10	About 4
100	Up to 100	About 7
1000	Up to 1000	About 10

Linear search grows directly with list size. Binary search grows slowly because it halves the list each time.

Final Time Complexity

Time Complexity: O(n) for Linear Search, O(log n) for Binary Search

This means linear search checks every item in the worst case, while binary search quickly narrows down the search by splitting the list.

Common Mistake

[X] Wrong: "Binary search works on any list, sorted or not."

[OK] Correct: Binary search only works correctly if the list is sorted, because it relies on dividing the list based on order.

Interview Connect

Knowing when to use linear or binary search shows you understand how to pick the right tool for the job, a key skill in coding interviews and real projects.

Self-Check

"What if the list is sorted but stored as a linked list instead of an array? How would that affect the time complexity of binary search?"