Time complexity of algorithms in java

Question

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);
}

"can it be specific for my array?" I'm sorry. I don't understand this sentence. — The Real Baumann
– The Real Baumann, Commented Feb 2, 2012 at 18:21
I'm upvoting this because while there are a lot of resources out on the net, I know I had a hard time grasping some of the concepts when I was learning about time complexity. — Brian Roach
– Brian Roach, Commented Feb 2, 2012 at 18:23

Kerrek SB · Accepted Answer · 2012-02-02 18:21:02Z

6

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.)

answered Feb 2, 2012 at 18:21

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

M9A Over a year ago

Yes checking the number of operations is what I meant. How can I do this?

hvgotcodes Over a year ago

i would add that the concept is language agnostic

Kerrek SB Over a year ago

@Matt9Atkins: As I said, add a counter variable somewhere, and increment it each time you do a comparison (e.g. just before the if).

Greg Hewgill · Accepted Answer · 2012-02-02 18:19:51Z

3

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.

answered Feb 2, 2012 at 18:19

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

1 Comment

hvgotcodes Over a year ago

i would add that the concept is language agnostic.

NPE · Accepted Answer · 2012-02-02 18:27:25Z

1

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.

edited Feb 2, 2012 at 18:27

answered Feb 2, 2012 at 18:22

NPE

503k114 gold badges970 silver badges1k bronze badges

Comments

Amir Afghani · Accepted Answer · 2012-02-02 18:22:06Z

0

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.

answered Feb 2, 2012 at 18:22

Amir Afghani

38.7k17 gold badges87 silver badges128 bronze badges

Collectives™ on Stack Overflow

Time complexity of algorithms in java

4 Answers 4

3 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related