Description
1. (20 points) Ordering functions
Arrange the following functions in order from the slowest growing function to the fastest growing
function. Briefly justify your answers.
√
n, np
lg n, 2
√
lg n
,(lg n)
2
2. (10 points) Properties of asymptotic notation
Let f(n), g(n), and h(n) be asymptotically positive and monotonically increasing functions. For each of
the following statements, decide whether you think it is true or false and give a proof or a counterexample.
(a) If f(n) = Ω(h(n)) and g(n) = O(h(n)), then f(n) = Ω(g(n)).
(c) If f(n) = O(g(n)), then 3f(n)
is O(3g(n)
).
3. (20 points)
The Body Mass Index (BMI) of a child at 5 years of age is a good indicator of future chances of
childhood obesity. Arlington Pediatrics maintains a list of BMI for all their 5-year old patients for an
entire year. Given a 5-year old’s BMI today, it computes the child’s BMI percentile as the ratio of the
number of 5-year old patients last year whose BMI is lesser than it, and the total number of patients in
last year’s record. At the end of the year, it updates its BMI list to prepare for the next year.
Polly’s intuition is that the binary search algorithm is a good inspiration for this problem.
1
(a) Explain briefly in words how you will solve this problem.
(b) Provide the pseudo-code for an algorithm to compute a child’s percentile BMI. Be sure to state
precise the inputs and outputs to the algorithm, and any assumptions about them.
(c) Prove the correctness of your algorithm.
You will be graded on (a) the precision of how you have stated your algorithm (b) the validity and
precision of your proof of correctness.
2
