Question

Using sorting as an algorithm solving specific problem and compare their method of solving it and performances’ tradeoffs in terms of its time complexity. compare its performance using different approaches (three approaches) such as (divide and conquer, dynamic programming, brute force, greedy approach ). show which approach solve the problem best.

Use sorting as an example and compare .

Answer 1

Sorting an array is the process of arranging the array elements such as to arrange them in a certain order for example in decreasing or increasing order.

Let us take three methods.

1. Brute Force : In the brute force approach we compare all possible pairs of elements to order them into the correct order. Since for every element we compare it with all other elements, for an array of length , every element will be compared with n other elements. So  
O(n2)
comparisons are required. So in the worst case, time complexity of this algorithm will be
O(n2)
. Bubble sort, selection sort, insertion sort are some examples of a sorting algorithm based on this paradigmn.

2. Divide and conquer: For algorithms using this paradigm, we first keep on dividing the array into smaller and smaller units and then when only one elements is left we start merging them. Let us see how we calculate the time complexity of this algorithm, Merge sort is an example of such a sorting algorithm. Let us analyze this algorithm's time complexity.

Since for merge sort, we have   $\small T(N) = 2 T(\frac{N}{2}) + c$

c is the constant time for all fixed time operations.Using masters theorem we get the time complexity of merge sort in worst case to be .

Onlogn

3. Tree or heap structure sorts: This also takes
O(nlogn)
time complexity. Heap sort creates a heap of the element. Heap is a structure that has the property that the parent is larger than both the children. First we construct the heap and we then remove the largest element and place it at the end of the sorted list. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array and goes on till there is no element left in the heap. Since the heap is a full binary tree so its height is of the order  
logV
. and we create a heap for every element so it takes the order
O(nlogn)
.