Miniquiz 10                                                         Name:
 11/14/2002                                                            Section:
 Time : 5 minutes
 

 Consider the following function

 static float findWinningProbability(ArrayList a, ArrayList b, ArrayList c)
{
   int totalOutcomeCount;
   int favourableOutcomeCount;
   Iterator itr1,itr2,itr3;
   int n1,n2,n3;
   totalOutcomeCount=a.size()*b.size()*c.size();
   favourableOutcomeCount=0;
   itr1=a.iterator();
   while(itr1.hasNext())
   {
     n1=((Integer)itr1.next()).intValue();
     itr2=b.iterator();
     while(itr2.hasNext())
     {
       n2=((Integer)itr2.next()).intValue();
       itr3=c.iterator();
       while(itr3.hasNext())
       {
         n3=((Integer)itr3.next()).intValue();
         if(n1<=n2+n3)
           favourableOutcomeCount++;
       }
      }
    }
    if(totalOutcomeCount==0)
        return 0;
    return ((float)favourableOutcomeCount)/totalOutcomeCount;
  }
}



P.T.O.





Find the running-time complexity of the above function. In particular, find
the running-time complexity when each of arraylist has a size n.
Rememeber that we are not worried about constant factors and other
slowly growing terms. We just want the term which dominates when n
grows very large.


Answer :



Here goes the motivation for above code:

Consider the following game. Assume that you are given three boxes A,B,C,
each having a bunch of balls. Each ball has a number written on it. A player
picks 1 ball from each box at random. If the number picked from box
A is less than or euqal to the sum of numbers picked from boxes B and
C, the player wins, otherwise the player loses. As a programmer, you have been
assigned that task of writing a function which takes 3 arraylists as input
representing the numbers in the boxes A,B,C respectively, and returns as output
the probability a player playing the game will win.
In particular, the probability p of the above event is defined as

  p= favourable outcomes/total number of outcomes.

which is exactly what the function findWinningProbability() calculates.