CMI2013-A-10

Question

The below question is based on following program:

procedure mystery (A : array [1..100] of int)
    int i,j,position,tmp;
    begin
        for j := 1 to 100 do
            position := j;
            for i := j to 100 do
                if (A[i] > A[position]) then
                    position := i;
                endfor
            tmp := A[j];
            A[j] := A[position];
            A[position] := tmp;
        endfor
end

The number of times the test $A[i] > A[\text{position}]$ is executed is:

• A. $100$
• B. $5050$
• C. $10000$
• D. Depends on contents of $A$

Comments

This procedure is similar to selection sort to sort in descending order. maximum element in the unsorted part will be swapped with first element. Array is divided into two parts between sorted and unsorted. After each pass of outer loop, sorted part is increasing and unsorted part decreasing.

$T(n) = T(n-1) + n$

answer will be $\frac{n*(n+1)}{2} = 5050$

---

@ Manu Thakur how did you wrote this T(n) please explain.??

---

If problem size is n(size of the unsorted half is n) then after complete iteration of inner for loop(which will run for n times) , size of the unsorted part will be reduced by 1(we will have the greatest element of the unsorted part at the left most position hence size of the unsorted part will be n-1 ).  Hence ,

T(n)=T(n−1)+n    [  T(n-1) time for reduced problem size and n for the execution of inner for loop n times] 

 

 

Answer 1

Answer: $5050  \ ( 100 +99 + 98 + ..... +1 = (100 *101)/2)$

Answer 2

for i=1.. Inner Loop will run 100 times

for i=2.. Inner Loop will run 99 times

...

...

for i=100.. Inner Loop will run 1 time.

so total no of time given statement executed is 1+2+...+100= (100*101)/2=5050

Comments

what will be worst case time complexity? please explain/.,

Answer 3