51
$\begingroup$

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers:

void F3() {
    for (int i = 1; i < n; i++) {
        if (A[i-1] > A[i]) {
            swap(i-1, i)
            i = 0
        }
    }
}

It may not be clear, but here $n$ is the size of the array A that we are trying to sort.

In any case, the teaching assistant explained to the class that this algorithm is in $\Theta(n^3)$ time (worst-case, I believe), but no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $\Theta(n^2)$ and not $\Theta(n^3)$.

Would someone be able to explain to me why this is $Θ(n^3)$ and not $Θ(n^2)$?

$\endgroup$
  • $\begingroup$ You may be interested in a structured approach to analysis; try to find a proof yourself! $\endgroup$ – Raphael Jan 18 '17 at 7:09
  • $\begingroup$ Just implement it and measure to convince yourself. An array with 10,000 elements in reversed order should take many minutes, and an array with 20,000 elements in reversed order should take about eight times longer. $\endgroup$ – gnasher729 Jan 18 '17 at 8:54
  • $\begingroup$ @gnasher729 You are not wrong, but my solution is different: if you try to prove your $O(n^2)$ bound you will invariably fail, which will tell you somethings amiss. (Of course, one can do both. Plotting/fitting is definitely faster for rejecting hypothesis, but less reliable. As long as you do some kind for formal/structured analysis, no harm done. Relying on plots is where trouble starts.) $\endgroup$ – Raphael Jan 18 '17 at 21:31
  • 1
    $\begingroup$ because of the i = 0 statement $\endgroup$ – njzk2 Jan 20 '17 at 3:08
61
$\begingroup$

This algorithm can be re-written like this

  1. Scan A until you find an inversion.
  2. If you find one, swap and start over.
  3. If there is none, terminate.

Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the pattern-matching approach many succumb to!

Nota bene: One has to be a little careful: some inversions appear early, some late, so it is not per se trivial that the costs add up as claimed (for the lower bound). You also need to observe that swaps never introduce new inversions. A more detailed analysis of the case with the inversely sorted array will then yield something like the quadratic case of Gauss' formula.

As @gnasher729 aptly comments, it's easy to see the worst-case running time is $\Omega(n^3)$ by analyzing the running time when sorting the input $[1, 2, \dots, n, 2n, 2n-1, \dots, n+1]$ (though this input is probably not the worst case).

Be careful: don't assume that a reversely-sorted array will necessarily be the worst-case input for all sorting algorithms. That depends on the algorithm. There are some sorting algorithms where a reversely-sorted array isn't the worst case, and might even be close to the best case.

$\endgroup$
  • 14
    $\begingroup$ If you take an array where the first half consists of the numbers 1 to n/2 in ascending order, and the second half is n to n/2 + 1 in reversed order, then it is obvious that you need at least n/2 steps to find each inversion, and there will be about (n/2)^2 / 2 of them. And that's most likely not the worst case. $\endgroup$ – gnasher729 Jan 18 '17 at 8:52
  • $\begingroup$ @AnthonyRossello It's a standard result (in combinatorics of permutations). In short, count the number of inversions in the reversely sorted array (is it obvious that that is the worst case?); it's a Gauss sum. $\endgroup$ – Raphael Jan 18 '17 at 9:03
  • $\begingroup$ One has to remember that no matter what, partial sums of $\Theta(n^\alpha)$ are always $\Theta(n^{\alpha+1})$, it's just the coefficient that drops rapidly: $\sum_{k=0}^n k^\alpha \sim \frac{1}{\alpha+1} n^{\alpha+1}$ (note the quite large coefficient $\frac{1}{\alpha+1}$). The trouble is, $\Theta$ does not care about coefficients. $\endgroup$ – yo' Jan 19 '17 at 19:17
  • 2
    $\begingroup$ @yo' And this relates to the answer (or the question) how? $\endgroup$ – Raphael Jan 19 '17 at 19:38
7
$\begingroup$

An alternative way of thinking about this is what the maximum value of i becomes before it is reset. This, as it turns out, makes it more straightforward to reason about how the prior sort order of A affects the run time of the algorithm.

In particular, observe that when i sets its new maximal value, let's call it N, the array [A[0], ..., A[N-1]] is sorted in ascending order.

So what happens when we add the element A[N] to the mix?

The mathematics:

Well, lets say it fits at position $p_N$. Then we need $N$ loop iterations (which I'll denote $\text{steps}$) to move it to place $N-1$, $N + (N-1)$ iterations to move it to place $N-2$, and in general:

$$\text{steps}_N(p_N) = N + (N-1) + (N-2) + \dots + (p_N+1) = \tfrac{1}{2}(N(N+1) - p_N(p_N+1))$$

For a randomly sorted array, $p_N$ takes the uniform distribution on $\{0, 1,\dots, N\}$ for each $N$, with:

$$\mathbb{E}(\text{steps}_N(p_N)) = \sum_{a=1}^{N} \mathbb{P}(p_N = a)\text{steps}_N(a) = \sum_{a=1}^{N}\tfrac{1}{N}\tfrac{1}{2}(N(N+1) - a(a+1)) = \tfrac{1}{2} ( N(N+1) - \tfrac{1}{3}(N+1)(N+2)) = \tfrac{1}{3} (N^2-1) = \Theta(N^2)$$

the sum can be shown using Faulhaber's formula or the Wolfram Alpha link at the bottom.

For an inversely sorted array, $p_N=0$ for all $N$, and we get:

$$\text{steps}_N(p_N) = \tfrac{1}{2}N(N+1)$$

exactly, taking strictly longer than any other value of $p_N$.

For an already sorted array, $p_N = N$ and $\text{steps}_N(p_N) = 0$, with the lower-order terms becoming relevant.

Total time:

To get the total time, we sum up the steps over all the $N$. (If we were being super careful, we would sum up the swaps as well as the loop iterations, and take care of the start and end conditions, but it is reasonably easy to see they don't contribute to the complexity in most cases).

And again, using linearity of expectation and Faulhaber's Formula:

$$\text{Expected Total Steps} = \mathbb{E}(\sum_{N=1}^n \text{steps}_N(p_N)) = \sum_{N=1}^n \mathbb{E}(\text{steps}_N(p_N)) = \Theta(n^3)$$

Of course, if for some reason $\text{steps}_N(p_N)$ is not $\Theta(N^2)$ (eg the distribution of arrays we're looking at are already very close to being sorted), then this need not always be the case. But it takes very specific distributions on $p_N$ to achieve this!

Relevant reading:

$\endgroup$
  • $\begingroup$ @Raphael - thanks for the suggested improvements, I've added a little more detail. Well the random variables are the $p_i$ (from $\Omega$, the set of orderings of A), so the expectations are technically done over $\Omega$ $\endgroup$ – David E Jan 18 '17 at 13:59
  • $\begingroup$ Different $\Omega$; I meant the Landau one. $\endgroup$ – Raphael Jan 19 '17 at 7:45
3
$\begingroup$

Disclaimer:

This is not a proof (it seems that some people think I posted it as if it was). This is only a small experiment that the OP could perform to resolve his or her doubts about the assignment:

no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $Θ(n^2)$ and not $Θ(n^3)$.

With such a simple code, the difference between $\Theta(n^2)$ and $\Theta(n^3)$ shouldn't be hard to spot and in many practical cases this is a useful approach to check hunches or adjust expectations.


@Raphael answered your question already, but just for kicks, fitting this program's output to $f(x) = a\cdot x^b + c\cdot x$ using this gnuplot script reported exponent values of $2.99796166833222$ and $2.99223727692339$ and produced the following plots (the first is normal scale and the second is log-log scale):

normal loglog

I hope this helps $\ddot\smile$

$\endgroup$
  • 2
    $\begingroup$ You can fit any function to these values. See also here. $\endgroup$ – Raphael Jan 18 '17 at 12:21
  • 3
    $\begingroup$ @Raphael If you wan't to nitpick in this way, then no, you can't fit any function (for example you won't be able to fit a constant function to any reasonable accuracy). This is not a proof, but there is already an answer which provides a sketch. As for the usefulness, I can quote your own post that you linked: "I have to agree that this is a very useful approach that is even sometimes underused". Moreover, the OP said he thought it should be $\Theta(n^2)$ rather than $\Theta(n^3)$, so why not to experiment and see whether his hunch was correct? Cont. $\endgroup$ – dtldarek Jan 18 '17 at 13:36
  • 2
    $\begingroup$ This provides evidence that the algorithm is $\Theta(n^3)$ but the question asks why. It's asking for an explanation of the phenomenon, not a confirmation of it. $\endgroup$ – David Richerby Jan 18 '17 at 14:47
  • 2
    $\begingroup$ @DavidRicherby Does this mean this answer is not useful? $\endgroup$ – dtldarek Jan 18 '17 at 14:51
  • 3
    $\begingroup$ @Magicsowon It's a question and answer site, not a forum. We're looking for answers to the question, not discussion around it. $\endgroup$ – David Richerby Jan 19 '17 at 15:20
3
$\begingroup$

Assume you have an array.

array a[10] = {10,8,9,6,7,4,5,2,3,0,1}

Your algorithm does the following

Scan(1) - Swap (10,8) => {8,10,9,6,7,4,5,2,3,0,1}  //keep looking at "10"
Scan(2) - Swap (10,9) => {8,9,10,6,7,4,5,2,3,0,1}
...
Scan(10) - Swap(10,1) => {8,9,6,7,4,5,2,3,0,1,10}

Basically it moves to the end of the array the highest element, and in doing that it start overs at each scan effectively doing O(n^2) moves.. just for that one element. However, there are n elements so we'll have to repeat this n times. This isn't a formal proof, but it helps understand in an "unformal" way why the running time is O(n^3).

$\endgroup$
  • 4
    $\begingroup$ What does this add over other answers? An explanation of what the algorithm does was already given, and your reasoning for the runtime is sketchy at best. (Worst-case does not behave linearly!) $\endgroup$ – Raphael Jan 18 '17 at 12:20
  • 2
    $\begingroup$ Sometimes there is value in explaining the same idea in multiple ways (with formalism; with a simple example to "pump the intuition"), especially when person asking the question is new to the field. So it seems to me what this adds is that it's presented in a way that might aid the intuition. $\endgroup$ – D.W. Jan 19 '17 at 19:29
  • $\begingroup$ Since I got a reply to my comment in a flag (don't do that!): "Worst-case does not behave linearly!" -- I mean the algebraic properties of the worst-case operator. Roughly speaking, you are using WorstCase(1+...+n) "=" WorstCase(1) + ... + WorstCase(n) but this identity does not hold. $\endgroup$ – Raphael Jan 19 '17 at 19:44
  • 1
    $\begingroup$ I'm new to this field and providing an explanation with a concrete, spelled-out example definitely helped me gain intuition about the problem. Now the accepted solution makes more sense to me. $\endgroup$ – vaer-k Jan 24 '17 at 17:20
0
$\begingroup$

The logic seems to be sorting the elements in the array in a ascending order.

Suppose the smallest number is at the end of the array(a[n]). For it to come to its right place - (n + (n-1) + (n-2) + ... 3 + 2 + 1) operations are required. = O(n2).

For a single element in the array O(n2) ops are required. So, for n eements it is O(n3).

$\endgroup$
  • 5
    $\begingroup$ What does this add over other answers? An explanation of what the algorithm does was already given, and your reasoning for the runtime is sketchy at best. (Worst-case does not behave linearly!) $\endgroup$ – Raphael Jan 18 '17 at 12:22
  • $\begingroup$ Great explanation. This provides a different, more intuitive perspective on the problem, not explained in other answers. (Not to mention very short and easy to understand.) $\endgroup$ – 2501 Jan 18 '17 at 20:37
  • 1
    $\begingroup$ @2501 No, it's wrong. Try using this "intuition" on Dijkstra's algorithm and you'll get quadratic runtime (in the number of nodes), which is wrong. $\endgroup$ – Raphael Jan 18 '17 at 21:22
  • $\begingroup$ @Raphael No, it's right, as explained in the answer. This explanation works for this algorithm, not for others. While it may be wrong for them, this claim doesn't prove it is wrong for this one. $\endgroup$ – 2501 Jan 18 '17 at 22:37
  • $\begingroup$ @Raphael I did not understand the explanation in the accepted answer. So, I solved this and tried to explain it in simple terms without any technical terms.. so, this is for members like me who could not understand the accepted answer.. I am glad someone is finding this useful. $\endgroup$ – mk.. Jan 18 '17 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.