Time complexity of bubble sort with single for loop

Question

I studied that bubble sort is an O(n^2) algorithm. But I designed an algorithm which looks as O(n). The following is my code:

void bubbleSort(int[] arr) {
int counter = 1, i = 0;
int N = arr.length-counter;
for(i=0; i<N; ){
  if(arr[i]>arr[i+1]){
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
  }
  i++;
  if(i == N){
    N = arr.length - (++counter);
    i = 0;
  }
}

There is one for loop and the counter i is set when it is equal to N. According to me the loop is O(n) and it resets for n-1 times. So, it becomes O(n) + O(n-1) = O(n). Am I correct? If not what should be the complexity of this code.

Answer 1

No, you are not correct. Having one loop doesn't mean it's O(n). You have to take into consideration how many steps are executed.

Your loop gets re-initialized when i == N. You are right about - the loop gets re-initialized (n-1) times. Now each time loop is executed the then value of N times. So it's not O(n) + O(n-1) rather it's O(n*(n-1)) which eventually leads to O(n^2).

For example -

at first pass, loop will be executed (N) times. then N will be re-initialized to (N-1)
at second pass, loop will be executed (N-1) times. then N will be re-initialized to (N-2)
...
...
this will go on in total of (n-1) times.

So it will be - O(N + (N - 1) + (N - 2) + ... + 1), which will be evaluated into O(n^2)

For experimental purpose you can initialize a counter globally. and check what's the value of total steps executed by your program to check what's actually going on -

void bubbleSort(int[] arr) {
int counter = 1, i = 0;
int total = 0;
int N = arr.length-counter;
for(i=0; i<N; ){
  total++;
  if(arr[i]>arr[i+1]){
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
  }
  i++;
  if(i == N){
    N = arr.length - (++counter);
    i = 0;
  }
}
printf(%d", total); // this will give you total number of steps executed. check for various value of n