Binary Search vs Linear Search Real Cost Difference in DSA Go - 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 fast two common search methods work when looking for a number in a list.

Which method finds the number faster as the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippets for searching a number.

// Linear Search
func linearSearch(arr []int, target int) int {
  for i, v := range arr {
    if v == target {
      return i
    }
  }
  return -1
}

// Binary Search (array must be sorted)
func binarySearch(arr []int, target int) int {
  low, high := 0, len(arr)-1
  for low <= high {
    mid := (low + high) / 2
    if arr[mid] == target {
      return mid
    } else if arr[mid] < target {
      low = mid + 1
    } else {
      high = 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 search method.

• Linear Search primary operation: Checking each element one by one.
• Linear Search how many times: Up to n times, where n is the list size.
• Binary Search primary operation: Checking 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

Compare how many checks each method does 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

Pattern observation: Linear search grows directly with list size, doubling the list doubles the work. Binary search grows slowly, adding one more check roughly doubles the list size.

Final Time Complexity

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

Linear search checks every item, so time grows with list size. Binary search cuts the list in half each step, so time grows very slowly even for big lists.

Common Mistake

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

[OK] Correct: Binary search only works on sorted lists because it decides which half to search next based on order. If the list is not sorted, it can miss the target.

Interview Connect

Knowing when to use linear or binary search shows you understand how to pick the right tool for the job. This skill helps you write faster programs and impress interviewers with clear thinking.

Self-Check

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