Linear Search Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Linear Search Algorithm

O(n)

Understanding Time Complexity

We want to understand how the time taken by linear search changes as the list size grows.

How many steps does it take to find an item or decide it's not there?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // found target
        }
    }
    return -1; // target not found
}
    

This code looks through each element 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.

How Execution Grows With Input

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

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

Pattern observation: The steps increase directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the target grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Linear search always takes the same time no matter the list size."

[OK] Correct: The search time depends on where the target is or if it is missing, so bigger lists usually take more steps.

Interview Connect

Understanding linear search time helps you explain why more efficient methods exist and shows you can analyze simple algorithms clearly.

Self-Check

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