Binary Search vs Linear Search Real Cost Difference in DSA Typescript - 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 in speed depending on the method used.

Which method is faster as the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of these two search methods.

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

function binarySearch(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const 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 and checks the middle repeatedly on a sorted list.

Identify Repeating Operations

Look at what repeats in each method.

• Linear Search: One loop checking each element from start to end.
• Binary Search: A loop that halves the search space each time by checking the middle element.
• Dominant operation: Comparing elements to the target value.

How Execution Grows With Input

How many checks happen as the list size grows?

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

Linear search grows directly with list size. Binary search grows slowly because it cuts the list in half each time.

Final Time Complexity

Time Complexity: O(n) for linear search, O(log n) for binary search

Linear search checks each item one by one, so time grows with list size. Binary search quickly narrows down the search, so time grows much slower.

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. Otherwise, it can miss the target or give wrong results.

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 and problem solving.

Self-Check

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