Consider the code fragment:

 public static int f5 (int n) { 
    if (n <= 1) return 1; 
    int i = 0;
    while (i < n)
      i++;

    return f5(n/2) + f5(n/2); 
 } 

As a function of N, what is the total number of addition operations? Assume N is a power of 2.

Consider three items a, b, and c. Assume that we'd like to establish their order using comparisons. Naturally, there are 6 orders: abc, acb, bac, bca, cab, cba. Below is shown a diagram of an optimal decision tree for determining the order of these three numbers.

We observe that the height of the decision tree must be at least three levels deep to accomodate the 6 leaf nodes.

Imagine now that we have 4 items. How many different permutations are possible for 4 items? Equivalently, how many leaf nodes would there by in the optimal decision tree (which you should NOT attempt to draw)?