Consider a new sorting algorithm similar to the bubble sort algorithm, called Rumble Sort.
Given an array as input, RumbleSort attempts to sort the array and produces a sorted array as output. Here's the pseudocode for RumbleSort (L):
RumbleSort(L):
let sorted = false
while not sorted:
sorted = true
for i = 0; i < len(L) -2; i ++:
if L[i]>L[i +2];
sorted =false.
reverse the given list from L{i} to L[i +2] (inclusive)
With regards to the above Rumble Sort algorithm, consider the following statements.
S1:Rumble Sort work's correctly for all inputs.
S2:The time complexity of detemining if the RumbleSort algorithm will work correctly for a given input is O(n2)
Which of the above statements is/are true?
S1is clearly false.
Now since we know how the algorithm works, the algorithm actually sorts the odd and even sublists separately. Hence we can mimic the action of this algorithm by using the best sorting technique which takes O(n logn ) time to sort the odd and even positions separately first. And to check if the given array is sorted takes O(n). Hence overall time complexity to check if the algorithm will work correctly for a given input is O(n logn) thus
S2 is also false.