1. If A is an array with n elements and procedure Swap exchanges its arguments,
ID: 3623629 • Letter: 1
Question
1. If A is an array with n elements and procedure Swap exchanges its arguments, then the following code segment sorts A in descending order.for (int j = 0; j < n-1; j++)
for (int k =0; k < n-j-1; k++)
if (A[k] < A[k+1])
Swap (A[k], A[k+1])
a. How many comparisons (counting only A[k] < A[k+1]) are made? Represent the complexity in term of number of comparison using a big-O notation.
b. Now lets evaluate the performance in term of calls to Swap (assuming only this function call matters – comparison no longer matter). What is the best and worst performance of the code in term of number of calls to Swap. Represent the complexity using a big-theta notation.
Explanation / Answer
Part A:
calculating number of comparisons:-
for each j belonging to [0,n-1),the inner loop runs n-j-1 times,so we have the number of times the inner loop runs can be given as:
for j=0 ,inner loop runs n-1 times.
for j=1,inner loop runs n-2 times.
for j=2,innet loop runs n-3 times.
.
.
.
for j=n-1,inner loop runs 0 times,
so simmply we can calculate the total number of comparison by adding all the terms i.e.
(n-1)+(n-2)+.........+2+1+0
the sum of this series is n(n-1)/2.
NOTE : this is the worst case comparison,means the array is already sorted in ascending order.
for average case,the number of comparisons will be n(n-1)/4.
hence we can say that the number of comparisons is O(n^2).
to prove ,we must have
(n^2-n)/2 <= cn^2 for some constant c > 0
so,
(2c-1)n^2+n >= 0
which is true for all n if 2c-1>=0 |the equality occurs when n=0;
i.e. c >= 1/2
hence c must belong to set [1/2,)
for (0,1/2], (2c-1)n^2+n <= 0
hence the number of comparisons are (n^2).
Part B:
call to swap will be O(n^2) times ,when the array is already sorted in ascending order,the WORST CASE.
so the worst case running time is (n^2).
in best case ,i.e. the array is sorted in descending order there will be no call to SWAP.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.