## 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 Selection Sort Time Complexity

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

## Binary Search Time Complexity

Binary Search finds the target value in an already sorted array by checking the center value. If the center value is not the target value, Linear Search selects the left or right sub-array and continues the search until the target value is found.

To find the time complexity for Binary Search, let's see how many compare operations are needed to find the target value in an array with $$n$$ values.

The best case scenario is if the first middle value is the same as the target value. If this happens the target value is found straight away, with only one compare, so the time complexity is $$O(1)$$ in this case.

The worst case scenario is if the search area must be cut in half over and over until the search area is just one value. When this happens, it does not affect the time complexity if the target value is found or not.

Let's consider array lengths that are powers of 2, like 2, 4, 8, 16, 32 64 and so on.

How many times must 2 be cut in half until we are looking at just one value? It is just one time, right?

How about 8? We must cut an array of 8 values in half 3 times to arrive at just one value.

An array of 32 values must be cut in half 5 times.

We can see that $$2=2^1$$, $$8=2^3$$ and $$32=2^5$$. So the number of times we must cut an array to arrive at just one element can be found in the power with base 2. Another way to look at it is to ask "how many times must I multiply 2 with itself to arrive at this number?". Mathematically we can use the base-2 logarithm, so that we can find out that an array of length $$n$$ can be split in half $$\log_{2}(n)$$ times.

This means that time complexity for Binary Search is

$\underline{\underline{O( \log_{2} n )}}$

The average case scenario is not so easy to pinpoint, but since we understand time complexity of an algorithm as the upper bound of the worst case scenario, using Big O notation, the average case scenario is not that interesting.

Note: Time complexity for Binary Search $$O( \log_{2}n)$$ is a lot faster than Linear Search $$O(n)$$, but it is important to remember that Binary Search requires a sorted array, and Linear Search does not.

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

## Binary Search Simulation

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

{{ this.userX }}

Operations: {{ operations }}

As you can see when running simulations of Binary Search, the search requires very few compares, even if the the array is big and the value we are looking for is not found.

×

## Contact Sales

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