## 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

## Linked Lists

DSA Linked Lists DSA Linked Lists in Memory DSA Linked Lists Types Linked Lists Operations

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

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

## Insertion Sort Time Complexity

The worst case scenario for Insertion Sort is if the array is already sorted, but with the highest values first. That is because in such a scenario, every new value must "move through" the whole sorted part of the array.

These are the operations that are done by the Insertion Sort algorithm for the first elements:

• The 1st value is already in the correct position.
• The 2nd value must be compared and moved past the 1st value.
• The 3rd value must be compared and moved past two values.
• The 3rd value must be compared and moved past three values.
• And so on..

If we continue this pattern, we get the total number of operations for $$n$$ values:

$1+2+3+...+(n-1)$

This is a well known series in mathematics that can be written like this:

$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$

For very large $$n$$, the $$\frac{n^2}{2}$$ term dominates, so we can simplify by removing the second term $$\frac{n}{2}$$.

Using Big O notation, we get this time complexity for the Insertion Sort algorithm:

$O(\frac{n^2}{2}) = O(\frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}}$

The time complexity can be displayed like this:

As you can see, the time used by Insertion Sort increases fast when the number of values is $$n$$ increased.

## Insertion Sort Simulation

Use the simulation below to see how the theoretical time complexity $$O(n^2)$$ (red line) compares with the number of operations of actual Insertion Sorts.

{{ this.userX }}

Operations: {{ operations }}

For Insertion Sort, there is a big difference between best, average and worst case scenarios. You can see that by running the different simulations above.

The red line above represents the theoretical upper bound time complexity $$O(n^2)$$, and the actual function in this case is $$1.07 \cdot n^2$$.

Remember that a function $$f(n)$$ is said to be $$O(g(n))$$ if we have a positive constant $$C$$ so that $$C \cdot g(n)>f(n)$$.

In this case $$f(n)$$ is the number of operations used by Insertion Sort, $$g(n)=n^2$$ and $$C=1.07$$.

×

## Contact Sales

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

## Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail:
help@w3schools.com

W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning. Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookie and privacy policy.

Copyright 1999-2024 by Refsnes Data. All Rights Reserved. W3Schools is Powered by W3.CSS.