CODEWITHSUNDEEP
javaarrayssortingtimecomplexity-theory
M9A
M9A

Reputation: 3276

Time complexity of algorithms in java

Hi I am using the following generic bubble sort algorithm and I would like to display the time complexity. I understand that the best/worst case for this algorithm is fixed but I was wondering, can it be specific for my array?

For example the worst case for this sort is O(n^2), can that be specific for my array?

For example, worst case can be sorting 100 of the 120 elements (thats what i mean by specific for my array).

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}

Upvotes: 0

Views: 944

Answers (4)

NPE
NPE

Reputation: 500207

In the general case, your algorithm's worst-case complexity is O(n^2) (i.e. no more than n^2, asymptotically). It is also Theta(n^2) (i.e. no more and no less than n^2). I am omitting the multiplicative constant.

Let's say you know something about your array. To keep things specific, let's say you know that your array requires no more than five bubblesort-type swaps to become sorted. With this knowledge, it is still correct to say that the run-time of your algorithm is O(n^2). It is, however, no longer Theta(n^2).

It is also correct to say that the run-time of the algorithm in that specific case is O(n). In other words, knowing something about the array has enabled us to provide a tighter bound on the runtime of your algorithm.

Upvotes: 1

Amir Afghani
Amir Afghani

Reputation: 38521

The best case for bubble sort occurs when the list is already sorted or nearly sorted O(n), so yes it can depend on your array.

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 476950

Complexity is an asymptotic property of a function (or an algorithm), and not of an actual execution path. Complexity expresses the relation between input size and computation time (or space requirement). As such, this concept has no meaning when applied to one single, concrete computation.

In other words, you can ask about the complexity of computing f(n) depending on n, but not of computing f(5). The latter is just a number. The former is a function.

What you can do instead is count the actual number of operations. Every time you perform an operation that you want to include (for example "comparisons"), just increment some global counter, and check its value afterwards. (The algorithmic complexity should tell you bounds for the values that this counter may take.)

Upvotes: 6

Greg Hewgill
Greg Hewgill

Reputation: 992797

The "worst case" performance of an algorithm refers to a set of input data that makes the algorithm behave most badly. So it doesn't make sense to refer to the "worst case" of a specific input array, because that is only one case.

Upvotes: 3

Related Questions