Time ComplexityLesson 45Free preview

Bubble Sort

This lesson is part of DSA · All levels

Summary

The complexity analysis of the bubble sort shows the number of comparisons around n(n-1)/2 in the worst case, so O(n^2) for the average and worst case. The best case can be implemented with an exchange marker. The memory is constant because the algorithm works in-place.

Key points

Worst case and average
The best case is when a marker is already sorted
The maximum number of comparisons is about n(n-1)/2
Space complexity O(1), in-place

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.