Question

Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an)

Answer 1

The algorithm will execute the inner and outer loops until i<j that means the loop will execute till the complete array of numbers is scanned and if after complete scan i.e. one complete iteration i<j (index i still remains less than index j) then the numbers on corresponding indices will be swapped.

sample code

int main() 1 2 { 3 4. 5 6 int a[] = {2, 3, -2, 0, -1, 1, 6}; int p = -1; int n = sizeof(a) / sizeof(int); int i = 1; int j = n - 1; int temp; while (i < j) 7 8 9 { while (i < j && a[i] < p) i = i + 1; while (i < j && a[j] >= p) j = j - 1; if (i < j) { 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 } temp = a[i]; a[i] = a[j]; a[j] temp; } Se for (int m = 0; m < n; m++) printf("\n%d", a[m]);

Solution(b):

As it can be clearly seen from the code snippet in part a solution that increment of i and decrement of j is dependent on the condition (i<j and a[i]<p) which means that the execution of these statements will depend on the input values given in the sequence list and not on the number of elements in the list.

The execution of statement i=i+1 or j=j-1 will be maximum when the array list is already sorted.

Example: {5,4,3,2,1,0} let p=0 (should be less than all elements in the list)

here i=i+1 will be executed n(5) times.

Similarly in {0,1,2,3,4,5} let p=0

here j=j-1 will be executed n times thus maximising the execution of these statements

Solution(C):

3) Yes answer depends on the numbers partially, because if the list is of all negative integers and p = 0 then i increases till the value of n and j = n, in that case no swap command is executed. If there are all positives, then j decreases to i and again no swapping. Swapping happens only when there is are balanced numbers in sequence. count = count of numbers less than pivot towards the end of sequence as in case of above example it is 2 as only 2 negative integers were at the end of sequence Swapping can happen maximum for n/2 numbers

Solution(d):

The asymptotic lower bound of the time complexity is omega(n) where n is the number of elements. It will be when the list is sorted as explained in part b solution.

The worst-case complexity is necessary to determine the maximum time taken by the algorithm to execute. As it is clearly seen from the algorithm the number of times i or j incremented in the worst case that many numbers of swaps are possible as it is under outer while(i<j) loop.

PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION