Exercise 1                                                            Math Refresher

Assume n is continuous

1. Calculate limn →∞

2. Calculate limn →∞   (where a > b, a > 0, and b > 0)

3. Calculate limn →∞

4. Please transform nlog n  into the form of a power of 2

5. Please compute the sum of the first consecutive n odd positive integers

6. The cost of building the first level of an apartment building is 5U, and each subsequent level is more expensive by 2U . How much is the total cost for building an apartment with ℓ levels? Please specify your answer in terms of ℓ and U .

Exercise 2                                                                  Time Complexity

Please derive the worst case total time required by the following algorithms, assuming they are executed in a RAM computational model. Please represent your total time in terms of the size of the input array (i.e., A.length). This total time is similar to the notation T(n) in InsertionSort analysis covered in the first two lectures. Please also provide the tight bound (i.e., Θ) of the total time.

Exercise 3                                                    Estimation of Input Size

Estimate the largest upper bound on the input size required for a modern computer (under the RAM model) to run an algorithm in 1 second, assuming the computer executes exactly one hundred million operations per second.

Exercise 4                                          Properties of Asymptotic Notations