i | ||
1 | 10 | 10 |
2 | 6 | 6 |
3 | 3 | 4 |
4 | 8 | 9 |
5 | 1 | 3 |
C=18 |
Hint: Let be the cost of the optimal binary search tree that contains the set of keys where . Show that
where is the mean and is the standard deviation of the distribution. Hint: Consider the central limit theorem .
where is the mean of the distribution.
Hint: Use the fact , where Z is an exponentially distributed random variable with mean .