## 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