Faculty of Engineering and Mathematical Sciences 
Not logged in (login)

help2200


This forum is provided to promote discussion amongst students enrolled in Data Structures and Algorithms (CITS2200).
 
Options:
RSS cloud
Jump to:

Proving the complexity of different sorts

1 of 251 articles shown, currently no other people reading this forum.
photo
From: ANONYMOUS
Date: Wed 1st Apr, 10:43am
Actions: 
        Login-to-reply
ANONYMOUS wrote:

> Hi,
> 
> How do you want us to prove the different sorts: Insertion,Merge and Quick. Do we 
need 
> to prove them mathematically?

I am not aware of anywhere in the unit content where you are asked to prove all these, 
but it is good to be interested.

Note that while analysing the worst case complexity is easy enough for all three 
algorithms, the expected complexity of quicksort is very challenging to prove and I 
believe is beyond the scope of this unit.

As an example, the below is a way of deriving the worst case complexity of insertion 
sort:

The worst case for insertion sort is a backwards list.
In this case, we will take each element, and have to shuffle every element before it 
over one by one.
As such, to put the element at index i into its appropriate spot, we will have to move 
i elements.
Moving each element is O(1), so moving them all takes O(i).
We have to do this for all 0 <= i < N, so we get 0 + 1 + 2 + ... + (N - 1).
There are a number of different proofs that 0 + 1 + 2 + ... + (N - 1) = N * (N - 1) / 
2.
This expands to (1/2) (N^2 - N).
We can ignore the constant factor, and the -N term will be dominated by N^2, so we find 
that this is O(N^2), as expected.

Some hints/notes for further proofs:

Insertion sort expected case: Similar to above, but we expect to only have to move some 
of the elements each time. On average, how many do we expect to move? Does this change 
the complexity by more than a constant factor?

Merge sort: Are the expected and worst cases for merge sort going to be different? 
Merge sort is a recursive algorithm so consider analysing it by defining a recursive 
time function T(N) for how long it takes to sort N elements?

Quick sort: The worst case for quick sort is similar to that of insertion sort. If our 
pivot is either the minimum or maximum element in the array, then we will only end up 
removing the pivot from our array each time, which only sorts one element at a time, 
like insertion sort.

The results you should be looking for:
Algorithm        Worst Case          Expected Case
Insertion        O(N^2)              O(N^2)
Merge            O(N log N)          O(N log N)
Quick            O(N^2)              O(N log N)

Related articles

Proving the complexity of different sorts (all 3) RSS
├─ original   Tue 24th Mar, 4:38pm, ANONYMOUS
├─ reply 1   Tue 24th Mar, 5:05pm, ANONYMOUS  O.P.
└─ THIS   Wed 1st Apr, 10:43am, ANONYMOUS
This Page


Program written by: [email protected]
Feedback welcome
Last modified:  8:27am May 24 2020