Linear Search Algorithm in DSA Typescript - Time & Space Complexity

Time Complexity: Linear Search Algorithm

O(n)

Understanding Time Complexity

We want to understand how long it takes to find a value in a list using linear search.

How does the time needed grow as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code looks through each item in the list one by one to find the target value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the array one by one.
• How many times: Up to n times, where n is the number of elements in the array.

How Execution Grows With Input

As the list gets bigger, the number of checks grows roughly the same amount.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of operations grows directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the target grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Linear search is always fast because it just checks items one by one."

[OK] Correct: If the target is near the end or not in the list, it has to check almost every item, which can take a long time for big lists.

Interview Connect

Understanding linear search time helps you explain why some searches are slow and when to use better methods, a key skill in coding interviews.

Self-Check

"What if the array was sorted and we used binary search instead? How would the time complexity change?"