Searching and Sorting Quiz 1

First Outer loop and second loop runs n time so it’s time complexity is O(n*n) and the inner most loop is increasing in multiples of two so it’s time complexity is O(logn ). Hence total time complexity is O((N2)*(log N))

Bubble sort need 4 iteration to sort the given array . Eventhough first two elements are already sorted.

To find all the pairs of shortest distance in a graph Bellman-Ford  algorithm is used.

Left element=8, right element=0,

Centre=[position(left+right)/2]=6.

The Quick sort is best suited to sort the array of 1 million elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst case behaviour and is almost always O(nlogn). And Quick sort requires little additional space and exhibits good cache locality.

Outer loop executes O(log n ) times and same as inner loop. So total time complexity is O(log n * log n)  = O(log2 n).

Quick sort is not a stable algorithm as it does not maintain the relative order of keys .

The total time complexity of heap sort is mathematically found as O(N log N).

Recursion is similar to a loop . Whatever programs we can make with recursion can also be possible through loops .

Merge Sort is the fastest stable sorting algorithm with worst-case complexity of O(n logn), but it requires extra space.