CODEWITHSUNDEEP
algorithmsortingtime-complexity
ortiv
ortiv

Reputation: 171

Worst case time complexity for this stupid sort?

The code looks like:

for (int i = 1; i < N; i++) {
    if (a[i] < a[i-1]) {
        swap(i, i-1);
        i = 0;
    }
}

After trying out a few things i figure the worst case is when the input array is in descending order. Then looks like the compares will be maximum and hence we will consider only compares. Then it seems it would be a sum of sums, i.e sum of ... {1+2+3+...+(n-1)}+{1+2+3+...+(n-2)}+{1+2+3+...+(n-3)}+ .... + 1 if so what would be O(n) ?

If I am not on the right path can someone point out what O(n) would be and how can it be derived? cheers!

Upvotes: 9

Views: 2395

Answers (3)

Timberwoof
Timberwoof

Reputation: 46

This is one half of the infamous Bubble Sort, which has a O(N^2). This partial sort has O(N) because the For loop goes from 1 to N. After one iteration, you will end up with the largest element at the end of the list and the rest of the list in some changed order. To be a proper Bubble Sort, it needs another loop inside this one to iterate j from 1 to N-i and do the same thing. The If goes inside the inner loop.

Now you have two loops, one inside the other, and they both go from 1 to N (sort of). You will have N * N or N^2 iterations. Thus O(N^2) for the Bubble Sort.

Now you have take your next step as a programmer: Finish writing the Bubble Sort and make it work correctly. Try it with different lengths of list a and see how long it takes. Then never use it again. ;-)

Upvotes: -2

templatetypedef
templatetypedef

Reputation: 372714

For starters, the summation

(1 + 2 + 3 + ... + n) + (1 + 2 + 3 + ... + n - 1) + ... + 1

is not actually O(n). Instead, it's O(n3). You can see this because the sum 1 + 2 + ... + n = O(n2, and there are n copies of each of them. You can more properly show that this summation is Θ(n3) by looking at the first n / 2 of these terms. Each of those terms is at least 1 + 2 + 3 + ... + n / 2 = Θ(n2), so there are n / 2 copies of something that's Θ(n2), giving a tight bound of Θ(n3).

We can upper-bound the total runtime of this algorithm at O(n3) by noting that every swap decreases the number of inversions in the array by one (an inversion is a pair of elements out of place). There can be at most O(n2) inversions in an array and a sorted array has no inversions in it (do you see why?), so there are at most O(n2) passes over the array and each takes at most O(n) work. That collectively gives a bound of O(n3).

Therefore, the Θ(n3) worst-case runtime you've identified is asymptotically tight, so the algorithm runs in time O(n3) and has worst-case runtime Θ(n3).

Hope this helps!

Upvotes: 7

recursive
recursive

Reputation: 86064

It does one iteration of the list per swap. The maximum number of swaps necessary is O(n * n) for a reversed list. Doing each iteration is O(n).

Therefore the algorithm is O(n * n * n).

Upvotes: 6

Related Questions