GATE Computer Science Engineering(CSE) 2027 Test: Divide & Conquer- 2 Free

Internal sorting is such a process that takes place entirely within the main memory of a computer. This is only possible whenever data items, to be sorted, is small enough to be accommodated in main memory. Hence, internal sorting do not need auxiliary storage.
External sorting is just opposite to interval sorting and used when input data, to be sorted, is very large. Hence, external sorting need auxiliary storage.

A sorting algorithm is said to be stable sorting algorithm if two objects /records with equal primary key appears in the same order in the sorted list as in the original unsorted list.

Randomized quick sort worst case time complexity = O (n²).

Binary search : T(n) = T(n/2) + 1
Merge sort : T(n) = 2T(n/2) + cn
Quick sort : T(n) = T(n - k) + T(k) + cn

Tower of Hanoi : T(n) = 2T(n - 1) + 1

Let, T(m, n) be the total number of steps.
So, T(m, 0) = 0, T{m, n) = T{n, m m o d n ) on average

The relation T(n) = T(n/4) + T(3n/4) + n The pivot element is selected in such a way that it will divide the array into 1/4th and 3/4th always solving this relation give 

We know that in balanced BST there are log₂n levels in both worst as well as best case where ‘n’ is number of elements

The recurrence tree for merge sort will have height n and O (n²) work will be done at each level of the recurrence tree (Each level involves ncomparisons and a comparison takes O(n) time in worst case). So time complexity of this merge sort will be O(n² logn).

In the worst case length of binary search tree can be O(n).
So insertion of an object will take O(n) time in worst case.

In worst case the pivot element position may be either first or last. In that case the elements are always divided in 1 : (n - 1) proportion. The recurrence relation for such a proportional division would be

In worst case the BST may be Skewed BST. This case occurs when we insert the elements in increasing order or decreasing order. Example: Consider we insert elements, in the order 1, 12, 39, 43, 50......
The BST would be

To find ‘n’ is the worst case we may have to traverse to bottom of tree which takes O(n) time.
Hence for both insertion and deletion worst case goes to 

Size sorted list has size 2, So, number of comparison is between min (2,2) to (2 + 2 - 1) = 3 So, 2, 3, 3 are number of comparisons.
So average number of comparison

Sequential to be organization suitable for batch processing and not suitable for interactive processing.

Recursive programs take more time than the equivalent non-recursive version and so not efficient. This is because of the function call overhead.
In binary search, since every time the current list is probed at the middle, random access is preferred. Since linked list does not support random access, binary search implemented this way is inefficient.