Question

In C++

1. How do you demo that selection sort has O(N²) complexity?

• Meaning of the O(N²). If you have N=1000 input values the selection sort need roughly 1000000 steps.
• What is the meaning of thee ‘step’ here? One ALU comparison, one swapping of values, or one calculation step on one value of the array.
• What is the total number of steps for selection sort?

Let me use an example N=5, to help me think

4+1-__

3+1-__

2+1-__

1+1-__

F(N)=__________________________

This is why we say the computational complexity O(N²)

As of now our algorithm has 50 elements. The number of steps should be around _________________.

If N-1000 the total number of steps is roughly 100,000

1G Hz means that in 1 second the computer can do calculation 100,000,000 times . this is why the execution is within 1 second

2. What is the sorting algorithm that have O(N²) complexity?
3. What are sorting algorithm that has other complexity?

Answer 1

Selection sort finds the minimum element in each iteration and places it at the beginning of the array( for ascending order). This is repeated until the entire array is sorted. At any point the beginning part of array is sorted and remaining is unsorted.

In each iteration it takes n steps to find the minimum and to place it the beginning. Now this is done for all n elements. So total time taken will be of the order n^2

Bubble sort, Selection sort,Insertion sort have O(n^2) complexity

Merge sort, Quick sort, Heap sort have O(n*logn) complexity

All the above are comparison based sorting algorithms. We also have linear sort algorithms like counting sort, bucket sort, radix sort. These have a time complexity of O(n) complexity