Average complexity -- worst case of an algorithm

[TheMathNoob]

Homework Statement

a Write an algorithm to find the median of three distinct integers a,b,c
b Describe D, the set of inputs for your algorithm, in light of the discussion in Section 1.4.3 following Example 1.9. This section discusses Average complexity for an algorithm which involves an understanding of random variables. Exercise 1.9 describes an array in which an algorithm must be written to find a certain value in the array. D describe the set of inputs. The book says that in this case the inputs can be categorized according to where in the array the value appears.
c How many comparisons does your algorithm do in the worst case? on the average?
d How many comparsions are necessary in the worst case to find the median of tree numbers? Justify your answer

Homework Equations

Average complexity=A(n) =∑Pr(I)t(I) the iterators for sigma is I∈D_n

t(I) is the number of basic operations performed by input I and Pr(I) represents the prob that I happens.
[/B]

The Attempt at a Solution

a)
int a;
int b;
int c;
int median;
if(a>b and a<c or a<b and a>c)
median =a;
else if(b>a and b<c or b<a and b>c)
median=b;
else
median=c;

b) Here I tried to categorize the events as the previous exercise.
I_i∈D_n

I1= the event in which the first comparison is true
I2= the event in which the second comparison is true and the previous ones are false (by logic)
I3= the event in which the third comparison is true and the previous ones are false (by logic)
I4= the event in which the forth comparison is true the previous ones are false

3) the compiler makes 4 comparisons in the worst case

Average=A(n)=∑Pr(I_i)t(_i) the iterator for sigma is 1≤i≤4

Pr(I_i) is equally likely to occur in any case because in total there are 6 possible outcomes like a<b<c, b<a<c etc and just one outcome will make the I_i happens.

so

Pr(I_i)= 1/6 for 1≤i≤4

t(_i)=i because if the compiler is reading the ith comparison then it should have read as well the previous comparisons.

A(n)=1/6*1+1/6*2+1/6*3+1/6*4=10/6=1.66

Note: This result will vary based on the compiler because compilers can take readings in different orders. In this case we are assuming that once the compiler sees the first comparison to be true then it doesn't look the second one.

Is all that right?

d) I did not get this part because to me, it looks the same as part c.

 

[mfb]

There are 6 possible outcomes, but you just have 4 cases. If every case would have probability 1/6, then with probability 2/6 you don't have any case? I think you are missing something here.

3) the compiler makes 4 comparisons in the worst case

"a>b and a<c" are two comparisons. The compiler won't make any comparison, but running the program will. A good compiler will probably write the code in such a way that "a<c" is not tested any more if "a>b" fails (because "X and Y" cannot be true if X is false). For "or", it works the other way round which you considered already.

You can reduce the number of necessary comparisons if you rewrite your code, but I don't know if optimizing it is part of the task.

 

[TheMathNoob]

There are 6 possible outcomes, but you just have 4 cases. If every case would have probability 1/6, then with probability 2/6 you don't have any case? I think you are missing something here.
"a>b and a<c" are two comparisons. The compiler won't make any comparison, but running the program will. A good compiler will probably write the code in such a way that "a<c" is not tested any more if "a>b" fails (because "X and Y" cannot be true if X is false). For "or", it works the other way round which you considered already.

You can reduce the number of necessary comparisons if you rewrite your code, but I don't know if optimizing it is part of the task.

Hi mfb, I did just 4 comparisons instead of doing six. As you can see in the block of the last else statement , it is logical to put two more unnecessary comparisons. How can you optimize that code?

 

[mfb]

Hi mfb, I did just 4 comparisons instead of doing six.

Sure, but you have more cases that can happen. All four (actually eight) comparisons can fail, that is another case (and it is more frequent than the other 4 you considered so far).

How can you optimize that code?

It is your homework problem. One possible start is "if(a>b) {".

 

[TheMathNoob]

mmmm I do not understand. Once the four comparisons fail, the compiler proceeds immediately to set median =c which is not a comparison. The average complexity in this case is just about comparisons.

Sure, but you have more cases that can happen. All four (actually eight) comparisons can fail, that is another case (and it is more frequent than the other 4 you considered so far).
It is your homework problem. One possible start is "if(a>b) {".

 

[mfb]

Once the four comparisons fail, the compiler proceeds immediately to set median =c which is not a comparison.

Sure, but the computer had to do all eight comparisons to get to this case.
Well, at least 6 even with optimization of the "and" evaluation. But certainly comparisons have been done if you set the median to c.

 

[TheMathNoob]

Sure, but the computer had to do all eight comparisons to get to this case.
Well, at least 6 even with optimization of the "and" evaluation. But certainly comparisons have been done if you set the median to c.

Ok, so what I have to do is to reconsider all 8 comparisons? and then try to find a way to optimize my code.

 

[mfb]

For numbers where c is the median, you need 6-8 comparisons right now.

Your algorithm is not wrong, and if that algorithm is not expected to run millions of times I would certainly write it that way because it is easy to read. You can reduce the number of comparisons, if you like, I don't think you have to. It would make the comparison between (c) and (d) nicer, however.

 

[TheMathNoob]

For numbers where c is the median, you need 6-8 comparisons right now.

Your algorithm is not wrong, and if that algorithm is not expected to run millions of times I would certainly write it that way because it is easy to read. You can reduce the number of comparisons, if you like, I don't think you have to. It would make the comparison between (c) and (d) nicer, however.

Thank you so much for your help!