Menu
×
   ❮   
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO W3.CSS C C++ C# BOOTSTRAP REACT MYSQL JQUERY EXCEL XML DJANGO NUMPY PANDAS NODEJS R TYPESCRIPT ANGULAR GIT POSTGRESQL MONGODB ASP AI GO KOTLIN SASS VUE DSA GEN AI SCIPY CYBERSECURITY DATA SCIENCE
     ❯   

DSA Bubble Sort Time Complexity


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


Bubble Sort Time Complexity

The Bubble Sort algorithm goes through an array of n values n1 times in a worst case scenario.

The first time the algorithm runs through the array, every value is compared to the next, and swaps the values if the left value is larger than the right. This means that the highest value bubbles up, and the unsorted part of the array becomes shorter and shorter until the sorting is done. So on average, n2 elements are considered when the algorithm goes through the array comparing and swapping values.

We can start calculating the number of operations done by the Bubble Sort algorithm on n values:

Operations=(n1)n2=n22n2

When looking at the time complexity for algorithms, we look at very large data sets, meaning n is a very big number. And for a very big number n, the term n22 becomes a lot bigger than the term n2. So large in fact, that we can approximate by simply removing that second term n2.

Operations=n22n2n22=12n2

When we are looking at time complexity like we are here, using Big O notation, factors are disregarded, so factor 12 is omitted. This means that the run time for the Bubble Sort algorithm can be described with time complexity, using Big O notation like this:

O(12n2)=O(n2)__

And the graph describing the Bubble Sort time complexity looks like this:

Bubble Sort time complexity

As you can see, the run time increases really fast when the size of the array is increased.

Luckily there are sorting algorithms that are faster than this, like Quicksort.


Bubble Sort Simulation

Choose the number of values in an array, and run this simulation to see how the number of operations Bubble Sort needs on an array of n elements is O(n2):

300

Operations: 0

 

The red line above represents the upper bound time complexity O(n2), and the actual function in this case is 1.05n2.

A function f(n) is said to be O(g(n)) if we have a positive constant C so that Cg(n)>f(n) for a large number of values n.

In this case f(n) is the number of operations used by Buble Sort, g(n)=n2 and C=1.05.

Read more about Big O notation and time complexity on this page.



×

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-2025 by Refsnes Data. All Rights Reserved. W3Schools is Powered by W3.CSS.