The algorithm below makes some changes to an input sequence of numbers. MysteryA

Question

The algorithm below makes some changes to an input sequence of numbers.

MysteryAlgorithm

Input: a1 (a sub 1) , a2 (a sub 2), ..., an (a sub n)
           n, the length of the sequence
           p, a number
Output: ??

i := 1
j := n

While (i < j)
           While (i < j and ai (a sub i) < p)
                     i := i + 1
            End-while
            While (i < j and aj (a sub j) < p)
                     j := j - 1
            End-while
            If (i < j)
                swap ai ( a sub i) and aj ( a sub j )
End-while

return(a1, a2,..., an)

a) Describe in English how the sequence of numbers is changed by the algorithm. (Hint: try the algorithm out on a small list of positive and negative numbers with p = 0)

b) What is the total number of times that the lines "i := i + 1" or "j := j - 1" are executed on a sequence of length n? Does your answer depend on the actual values of the numbers in the sequence or just the length of the sequence? If so, describe the inputs that maximize and minimize the number of times the two lines are executed.

c) What is the total number of times that the swap operation is executed? Does your answer depend on the actual values of the numbers in the sequence or just the length of the sequence? If so, describe the inputs that maximize and minimize the number of times the swap are executed.

d) Give an asymptotic lower bound for the time complexity of the algorithm. Is it important to consider the worst-case input in determining an asymptotic lower bound (using omega) on the time complexity of the algorithm? (Hint: argue that the number of swaps is at most the number of times that i is incremented or j is decremented).

e) Give a matching upper bound (using O-notation) for the time complexity of the algorithm.

Explanation / Answer

a) This algorithm, gets all the numbers less than pivot on one side of the sequence and the numbers greater than pivot on other side.

This algorithm can be used to sort data.

e.g., Sequence: 5,6,1,3,4,-1,-2

i = 1

j = 7

p=0

Iteration 1:

i<j: true

a[i] = 5

a[j] = -2

none of the while loop is executed as a[i] > p and a[j] < p

now a[i] and a[j] are swapped

Sequence becomes: -2,6,1,3,4,-1,5

Iteration 2:

a[i] = -2

As a[i]>p , hence i++

a[i] = 6

loop ends

Loop 2:

a[j]=5

As a[j]>p , hence j--

a[j] = -1

Now a[j]<p

swap a[j] and a[i]

Repeat the steps

and -2, -1, 1,3,4,6,5

#2: Yes answer depends on the actual values of the numbers, as shown in the example above, counters increase on the basis of the valueand the pivot

Maximum times i will be incremented when all the integers are negative in the sequence and pivot is 0, then it will iterate till end.

Minimum will be 0, when all are positive and pivot is 0.

vice versa for j

#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

#4: time complexity for Inner while loop will always be equal to n

to finish the loop, the counters will be executed n time.(i+j = n+1) and loop is executed till i<j hence, n times.

Lower bound = O(n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.