Last modified:
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not attempted" (not applicable). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
The purpose of this problem is to derive the optimal constant in front of the log by using the optimal base (instead of 2) in the definition of exponential height.
for all k >= 1.
Hint: Use an integral approximation to the summation; see pg. 1154 in CLRS.
is
Hint: Use (strong) induction on n and the fact you proved above.
Finally, we note that the quantity
is minimized when c is approximately 2.155, yielding a constant factor of 2.9882 in front of the lg n. This constant is provably as small as possible.