PS2 Part 2 Solutions

1. First part.
   1. It would take O(N) time since we might have to check each and every URL.

   2. It would take O(log N), since we can start in the middle. If the middle is the one we want then we return it. If the middle is bigger then we recursively check the first part. If the middle is smaller then we recursively check the second part. Since we are dividing by two each time, this will take O(log N) time.

      Update: Thursday September 09, 12:00PM H(m) should really be H(m) = 30*2^m because of the way I phrased the question. Also, if you used the number of seconds in a day, instead of the number of seconds in a month, you will not lose any points. Again, my question was ambiguous on this point.

   3. We first notice that the number of hits per month m, is given by H(m) where
      H(m) = 2^m
      The time to do a search is T(N) = O(N) = c * N. The example we have tells us that for N=250, the time is .1 seconds. That is,
      T(250) = .1 = c * 250
      therefore
      c = .0004
      which tells us that
      T(N) = .0005 * N

      Now, since the size of the file doubles each month, and it started at 250, this means that N will grow as a function of m. Specifically
      N(m) = 2^m/6 * 250.
      We can substitute this value into our equation for T(N) in order to get the time to execute a query as a function of the month:
      T(m) = .0004(250*2^m/6) = .1 * 2^m/6.

      We now have the number of hits and the time per hit as a function of the month. We now notice that the system will crash when the computer spends all the time doing searches. That is when
      H(m)*T(m) = Number of seconds in a month = 2592000 (assume 30 days in a month)
      which resolves to
      2^m* .1 * 2^m/6 = 2592000
      m= 21.1.

      So, our webserver will crash after 21.1 months.

   4. In this case we that H(m) is the same as before but:
      T(N) = c * log N
      T(250) = c * log 250
      T(N) = .04 * log N
      which means that:
      T(m) = .04*log(s^m/6 * 250)
      T(m) = .096 + .002m
      again we must solve
      H(m)*T(m) = Number of seconds in a month = 2592000 (assume 30 days in a month)
      which resolves to
      2^m*(.096 + .002m) = 2592000
      which works out to be m = 24.099.

   5. In this case H(m) still stays the same but T(N) = .1, which means that T(m) = .1. we then have
      2^^m * .1 = 2592000
      which means that m = 24.62.
   6. The basic assuption we are making is that all the hits will be evenly distributed throught the month. This is clearly not true since there will always be "rush hours". Therefore, it is very likely that the site will overload much sooner than these numbers lead us to believe.
2. 5.15a from the textbook.
   1. O(N)
   2. O(N²)
   3. O(N)
   4. O(N³)
   5. O(N²)
   6. O(N⁵)