## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# DSA Linear Search Time Complexity

See this page for a general explanation of what time complexity is.

## Linear Search Time Complexity

For a general explanation of what time complexity is, visit this page.

For a more thorough and detailed explanation of Insertion Sort time complexity, visit this page.

Linear Search compares each value with the value it is looking for. If the value is found, the index is returned, and if it is not found -1 is returned.

To find the time complexity for Linear Search, let's see if we can fins out how many compare operations are needed to find a value in an array with $$n$$ values.

Best Case Scenario is if the value we are looking for is the first value in the array. In such a case only one compare is needed and the time complexity is $$O(1)$$.

Worst Case Scenario is if the whole array is looked through without finding the target value. In such a case all values in the array are compared with the target value, and the time complexity is $$O(n)$$.

Average Case Scenario is not so easy to pinpoint. What is the possibility to finding the target value? That depends on the values in the array right? But if we assume that exactly one of the values in the array is equal to the target value, and that the position of that value can be anywhere, the average time needed for Linear Search is half of the time time needed in the worst case scenario.

Time complexity for Linear Search is $$O(n)$$.

If we draw how much time Linear Search needs to find a value in an array of $$n$$ values, we get this graph:

## Linear Search Simulation

Run the simulation for different number of values in an array, and see how many compares are needed for Linear Search to find a value in an array of $$n$$ values:

{{ this.userX }}

Operations: {{ operations }}

As you can see when running simulations of Linear Search, the search requires few compares if the value is found fast, but if the value we are looking for is not found, the maximum of compares are done.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com