CODEWITHSUNDEEP
performancealgorithmsorting
Arc Ranges
Arc Ranges

Reputation: 37

theoretical analysis of comparisons

I'm first asked to develop a simple sorting algorithm that sorts an array of integers in ascending order and put it to code:

int i, j;

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

        for (j = n - 2; j >0 ; j--)
            if(A[j] < A[j-1])
                swap(A, j-1, j);
    }

Now that I have the sort function, I'm asked to do a theoretical analysis for the running time of the algorithm. It says that the answer is O(n^2) but I'm not quite sure how to prove that complexity.

What I know so far is that the 1st loop runs from 0 to n-1, (so n-1 times), and the 2nd loop from n-2 to 0, (so n-2 times).

Doing the recurrence relation: 

let C(n) = the number of comparisons
for C(2) = C(n-1) + C(n-2)
         = C(1) + C(0)
    C(2) = 0 comparisons?
    C(n) in general would then be: C(n-1) + C(n-2) comparisons?

If anyone could guide my step by step, that would be greatly appreciated.

Upvotes: 1

Views: 73

Answers (2)

Filipe Gon&#231;alves
Filipe Gon&#231;alves

Reputation: 21213

Your analysis is correct: the outer loop makes n-1 iterations. The inner loop makes n-2.

So, for each iteration of the outer loop, you have n-2 iterations on the internal loop. Thus, the total number of steps is (n-1)(n-2) = n^2-3n+2.

The dominating term (which is what matters in big-O analysis) is n^2, so you get O(n^2) runtime.

I personally wouldn't use the recurrence method in this case. Writing the recurrence equation is usually helpful in recursive functions, but in simpler algorithms like this, sometimes it's just easier to look at the code and do some simple math.

Upvotes: 0

Johan S
Johan S

Reputation: 3591

When doing a "real" big O - time complexity analysis, you select one operation that you count, obviously the one that dominates the running time. In your case you could either choose the comparison or the swap, since worst case there will be a lot of swaps right?

Then you calculate how many times this will be evoked, scaling to input. So in your case you are quite right with your analysis, you simply do this:

C = O((n - 1)(n - 2)) = O(n^2 -3n + 2) = O(n^2)

I come up with these numbers through reasoning about the flow of data in your code. You have one outer for-loop iterating right? Inside that for-loop you have another for-loop iterating. The first for-loop iterates n - 1 times, and the second one n - 2 times. Since they are nested, the actual number of iterations are actually the multiplication of these two, because for every iteration in the outer loop, the whole inner loop runs, doing n - 2 iterations.

As you might know you always remove all but the dominating term when doing time complexity analysis.

There is a lot to add about worst-case complexity and average case, lower bounds, but this will hopefully make you grasp how to reason about big O time complexity analysis.

I've seen a lot of different techniques for actually analyzing the expression, such as your recurrence relation. However I personally prefer to just reason about the code instead. There are few algorithms which have hard upper bounds to compute, lower bounds on the other hand are in general very hard to compute.

Upvotes: 1

Related Questions