Complexity Analysis
Lesson 5 of 11 in Coddy's Bubble Sort course.
Complexity analysis of bubble sort.
Time complexity depends on the number of comparisons & swaps performed.
We have to perform n passes and in each pass we have (n-1) comparisons. where, n is the number of elements in the list.
Total comparisons=(n-1)+(n-1)+(n-1)....n times
=n*(n-1)
=n2-n
Time Complexity for bubble sort algorithm is O(n2).
If, we talk about Space complexity, no extra space is used in the algorithm, in-place sorting is being performed and elements are arranged in the original list itself.
Space Complexity for bubble sort algorithm is O(1) (Constant).
Challenge
EasyCreate a function named count_swaps that receives an array and size of the array. Perform bubble sort algorithm on the array and count number of times swapping is performed.
Try it yourself
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Write code here
return 0;
}
All lessons in Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm