Question:

Describe an optimal algorithm to find the second minimum number in an array of numbers. What is the exact number of comparisons required in the worst case?

Note that Big-Oh notation is not what is being asked. Exact number of comparisons is what is required.

Analysis:

Example array (here after called as arr) for the worst case:

20 | 15 | 16| 18| 19| 20

Say there are 6 #'s in an array.

for the array that has min of two #'s only you can start, unless they are equal #

so always for 2 #'s there will be minimum and a max of '1' comparison.

After comparing arr[0] and arr[1] you will assign a temp variable first = arr[0] and second = arr[2], you have to iterate the array forward and make comparison to the second and first.

Say you have an "if condition" for the new # like this.

if( new < second || new == second || new == first)

{

//case ignore

}

else

if( new > first) { second = first; first = new;}

else

if(new > second)

{

second = new;

}

or you can write the above as

if( new < second)

{

//case ignore

}

else

if( new > first) { second = first; first = new;}

else

if(new > second && new < first) -> to make sure new is not first, if not we will have first & second the same values...

{

second = new;

}

so second one was better comparison as it ignores one case, if you compare both the methods.

possibilities:

-------------------

any given new # will be equal to first or second in which case we do not care

or will be > first

or will be < second

or in between. -> worst case or new == first is the worst case.

so given 3 #'s worst case in a best algorithm will be:

5 comparisons.(for every new # 4 comparison + 1 comparison for the first two #'s)

2 # -> 1

3 # -> 5

4 # -> 9

5 # -> 13

This above is a series, where n+1 is greater than n by 4.

The above is a classic question and you have the answer. If the series is in the pattern above find the nth #. That would be the answer for the exact number of comparisons that needs to be made for the WORST case.

Ok it is (n-1) * 4 + 1

## No comments:

Post a Comment