Bubble Sort
For a general definition of time complexity, see the previous page.
Bubble Sort Time Complexity
The Bubble Sort method iterates over a set of n values. n−1. in the worst situation, several times.
Every value in the array is compared to every other value the first time the algorithm goes through it. If the left value is greater than the right, the values are switched. As a result, the array’s unsorted portion gets shorter and shorter until the sorting is complete, with the highest value bubbling up. Thus, generally speaking, n2.
When the algorithm iterates across the array, comparing and exchanging values, items are taken into account.
We can begin to determine how many operations the Bubble Sort algorithm performs on n values
===formula===
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.
===formula==
When we are looking at time complexity like we are here, using Big O notation, factors are disregarded, so factor 1/2 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:
===formula===
Additionally, the following graph depicts the Bubble Sort time complexity:
As you can see, as the array size increases, the run time grows very quickly.
Fortunately, faster sorting algorithms exist, such as 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):
===image===
The red line above represents the upper bound time complexity O(n2), and the actual function in this case is 1.05⋅n2.
A function f(n) is said to be O(g(n)) if we have a positive constant C so that C⋅g(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)=n2and C=1.05.
Visit this website to learn more about temporal complexity and Big O notation.
