1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Average complexity -- worst case of an algorithm

  1. Sep 26, 2015 #1
    1. The problem statement, all variables and given/known data
    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

    2. Relevant equations

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

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


    3. 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.
    Ii∈Dn

    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(Ii)t(i) the iterator for sigma is 1≤i≤4

    Pr(Ii) 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 Ii happens.

    so

    Pr(Ii)= 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 doesnt 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.
     
    Last edited: Sep 26, 2015
  2. jcsd
  3. Sep 27, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  4. Sep 27, 2015 #3
    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?
     
  5. Sep 27, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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) {".
     
  6. Sep 27, 2015 #5
    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.
     
  7. Sep 27, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  8. Sep 27, 2015 #7
    Ok, so what I have to do is to reconsider all 8 comparisons? and then try to find a way to optimize my code.
     
  9. Sep 27, 2015 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  10. Sep 27, 2015 #9
    Thank you so much for your help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Average complexity -- worst case of an algorithm
Loading...