0

I was trying out bubble sort. I want to figure out how to determine the Big(o) of a particular algorithm. 

public class BubbleSort {

    public int[] bubblesort(int[] numbers){
        int temp;
        for(int i =0; i< numbers.length; i++){
            for(int j = 1; j< numbers.length-i; j++){
                if(numbers[j-1] > numbers[j]){
                    temp = numbers[j-1];
                    numbers[j-1] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        return numbers;
    }

    public static void main(String args[]){
        int[] n = new int[]{4,3,2,1};

        long startTime = System.nanoTime();
        System.out.println(Arrays.toString(new BubbleSort().bubblesort(n)));
        long endTime = System.nanoTime();
        System.out.println("bubblesort : " + (endTime - startTime));
    }
}

The optimized bubble sort does this: 

compare & swap 4,3; compare & swap 4, 2; compare & swap 4, 1; start again 
compare & swap 3, 2; compare & swap 3, 1; start again 
compare & swap 2, 1; done

From Wiki i see that worst case analysis is O(n^2). how they came to a conclusion that the worst case analysis of this algorithm is O(n^2). I want to see this programmatically on how they are coming to worst case analysis of a giving algorithm.

The algorithm does EXACTLY (n^2) operations from what i understand, is there a way to programmatically get the result?

Matt Ball
  • 354,903
  • 100
  • 647
  • 710
Mathew
  • 231
  • 1
  • 4
  • 14
  • 4
    You cannot figure out asymptotic runtime *programmatically*, you figure it out mathematically. – Oliver Charlesworth Sep 28 '14 at 17:25
  • This is not an exact duplicate because it relates to a specific algorithm, for which it might be that an ad-hoc solution exists. –  Sep 28 '14 at 19:11
  • Actually, it is not unreasonable to feed the algorithm with ALL permutations of the sequence of the N first integers and count the comparisons and the swaps. This is doable for moderate N, say up to 10. The worst case values are easy to find, as well as best case and average case - assuming equiprobable permutations. As the behavior of this algorithm is very simple (two nested for loops), polynomial fitting will allow to measure the empirical behavior (in this case, even get the exact functions). –  Sep 28 '14 at 19:29
  • This may not be an exact duplicate, but it's nevertheless unclear what the OP is asking. – mjhm Sep 28 '14 at 19:50
  • Using the exhaustive method (feed all permutations for different `N`), you easily establish: best/average/worst comparisons: `(N-1)N/2`, `(N-1)N/2`, `(N-1)N/2` and swaps: `0`, `(N-1)N/2`, `(N-1)N/4`. It is by no means a proof for all `N`, but a helpful hint. –  Sep 28 '14 at 20:02

0 Answers0