Solution. Assuming the time grows as c n log n for some constant c, where log is base 2, we have c 10^4 log (10^4) = 16000. We are asked the value of x = c 10^5 log (10^5). Divide both equations to eliminate c, and we get x/16000 = 10 (5/4) = 12.5. Thus, x = 200000. Note: this example shows that the hidden constants in the big "Oh" notation do not matter for predictions.

Solution. Recall the Taylor series for e^x, and by grabbing just the 1000-th term, we have e^x > x^1000 /1000!. Thus, let us take a positive number b, and note that

    (n/b)^1000 /1000! < e^(n/b) = e^(n ln(1.001)) = 1.001^n

    n^1000 < C 1.001^n

Solution. The number of soltions is 5 (for the choices for median) times (4 choose 2) (for the selection of the two smaller elements out of the four remaining elements), or 5x6=30. There are thus at least 30 leaves in the decision tree. Since we use comparisons only, the decision tree is binary, and the lower bound is ceiling ( log_2 30 ) = 5. Note: With some work, one could get 6 as a lower bound. Start with one comparison, and note that each subtree has 18 leaves, for a lower bound of ceiling( 1 + log_2 18 ) = 6.

Solution. The statement is clearly true for n=1 and n=2. Assume it is true up to n-1, for general n. To show that the inequality is true for n, note the following:

       F(n) = F(n-1) + F(n-2)     (given)
            <= 2^(n-2) + 2^(n-3)  (hypothesis)
	    < 2^(n-2) + 2^(n-2)
	    = 2^(n-1).

Solution. The cells have two pointers to other cells underneath; a pointer "next" points to the neighboring cell in the stack; a pointer "max-next" points to the maximum in the cells underneath (itself included). Let value[.] be the value stored in a cell. We need to show that push and pop can be implemented' in O(1) time. The code is as follows, if S denotes a stack, and top[S] is a pointer to the top of S:

    report-max(S):  return value[max-next[top[S]]]
    push(x,S): create a cell c
	       next[c] = top[S] 
	       value[c] = x
               if x > value[max-next[top[S]]]
                 then max-next[c] = c
		 else max-next[c] = max-next[top[S]]
	       top[S] = c
    pop(S): top[S] = next[top[S]]

Solution. Let match (i,j) return true if a_i = i or a_(i+1)= i+1, ..., or a_j = j. We call this function once with match (1,n).

 match (i,j)
     if i > j then return false
     if i = j then if a_i = i then return true
                              else return false 
     if i < j then set m = floor ( (i+j)/2 )
                   if a_m = m then return true
                   if a_m > m then return match (i,m-1)
                   if a_m < m then return match (m+1,j)

Solution. Well, compute the preorder sequence number and postorder sequence number of each node, storing them in preorder[u] and postorder[u]. Now note that u is an ancestor of v if and only if preorder[u] <= preorder[v] and postorder[u] >= postorder[v]. So, the query can be answered in O(1) time.