CSE 5311 Spring 1998
Homework #1
Due: February 4, 1998

1. a.

      Search(A, k, p, r)                       COST     TIMES
         i = p                                  1         1
         while ((A[i] <> k) and (i <= r))       1        t1+1
            i = i + 1                           1         t1
         if i <= r                              1         1
         then return i                          1         1
         else return -1                         1         1

   b.

   T(n) = 1 + (t1+1) + t1 + 1 + 1 + 1

   c.

   The situation that will always result in the best-case run time is when the key k appears in the first element of the array. In this case the while loop is executed only once.

   Best Case T(n) = 1 + 2 + 1 + 1 + 1 + 1 = 7 =

   d.

   The situation that will result in the worst-case run time is when the key k appears only in the last element of the array. In this case the while loop is executed n times.

   Worst Case T(n) = 1 + (n+1) + n + 1 + 1 + 1 = 5 + n*(2) =

2. a.

      Search(A, k, p, r)                           COST     TIMES
         if (p <= r)                                1         1
         then i = (p+r)/2                           1         t1
              if (k == A[i])                        1         t1
              then return i                         1       t1*t2
              else if (k < A[i])                    1       t1*(1-t2)
                   then Search(A, k, p, i)        T(n/2)    t1*(1-t2)*t3
                   else Search(A, k, i+1, r)      T(n/2)    t1*(1-t2)*(1-t3)
         else return -1                             1        1-t1

   b.

   The situation that results in the best case is when the key k is found in position i halfway through the array. In this case the value of t1 is 1 and the value of t2 is 1. One of the worst-case situations is when k is found in the last element of the array (the maximum possible number of recursive calls must be made).

   c.

   

   Master method: a=1, b=2, f(n) = 4 = . This is case 2 because = 0. Thus T(n) = Theta(lgn).

3. The following chart shows the run time of algorithms that use f(n) operations to run on a computer where each opration takes one second to execute. Fill in the blanks in the chart.

   n f(n) = lg n f(n) = n f(n) = n lg n

   10 3.3s 10s 33.0s 100s 1024s

   20 4.3s 20s 86s 400s 291h

   50 5.6s 50s 280s 2500s (= 41.7min) 357,020 centuries

   100 6.6s 100s 660s (= 11min) 10,000s (= 2.78h)

   1,000 9.96s 1,000s 9960s (= 2.76h) 277.78h ***

   10,000 13.3s 10,000s (= 167min) 133000s (= 36.9h) 1,157 days ***

4. For each of the following, answer ``yes'', ``no'', or ``cannot tell''. Explain your reasoning.
   1. Is = O( )?

      No. In order for to be O( ), we would have to find c and such that for all n >= . Dividing each term by n, we see that we would need , which for any constant c will not be met as n grows beyond the value of c.

   2. Is = ( )?

      Yes. In order for to be ( ), we need to find c and such that for all n >= . Dividing each term by n yields , which is true for c = 1 and = 1.

5. Arrange the following expressions by growth rate from slowest to fastest.

   Arranged left-to-right as slowest to fastest growth rate we get

6. Give asymptotically tight upper and lower bounds for T(n) in each of the following currences. Assume that T(n) is constant for n <= 2. For each problem use two of the described methods to solve the recurrence.
   1. T(n) = 2T(n/2) + .

      Master

      a=2, b=2, f(n) = , = 1. This is case 3 with = 2. We need to show that 2f(n/2) <= cf(n) for c<1 and sufficiently large n. Show that 2*( ) <= c* , or 2( ) <= c , 1/4 <= c , which is true for c=1/2.

      Thus T(n) = .

      Iteration

      T(n) = + 2T(n/2)
      = + 2( + 2T(n/4))
      = + 2( + 2( + 2T(n/8)))
      = + + 4( + 2T(n/8)))
      The ith term is and the boundary case is reached when = 1, i >= .

      = or +
      = = = O( )

   2. T(n) = 3T(n-2) +

      Iteration

      

      The recursion will terminate when the argument to T() equals 1, i.e., n-2i = 1 or i = (n - 1)/2.

      

      Substitution

      First, show using the inductive hypothesis .

      

      Unfortunately, we cannot discard the without decreasing the righthand side and violating the inequality. So, we choose a different member of for T(n); namely, , where b is a constant. The inductive hypothesis is now .

      

      given that , or . Since this is a valid constant, .

      Next, show using the inductive hypothesis .

      

      since we can subtract from the righthand side without violating the inequality. Therefore, , and .

   3. T(n) = 3T(n/3) +

      Master

      a=3, b=3, f(n) = , = 1. This is case 1 where = 1. T(n) = .

      Iteration

      

      The recursion will terminate when the argument to T() equals 1, i.e., , or , or .

      

      Substitution

      First, show using the inductive hypothesis .

      

      Unfortunately, we cannot discard the without decreasing the righthand side and violating the inequality. So, we choose a different member of O(n) for T(n); namely, , where b is a constant. The inductive hypothesis is now .

      

      given that , or . Since this is a valid constant, T(n) = O(n).

      Next, show using the inductive hypothesis .

      

      The last step is valid since we can always reduce the righthand side of the inequality. Therefore, , and .

• About this document ...