http://i67.tinypic.com/spal1f.jpg a) Describe in English how the sequence of num
ID: 3606867 • Letter: H
Question
http://i67.tinypic.com/spal1f.jpg
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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.