/Discuss this assignment. /Solutions.

# 1. Bureaucratic part

This part you will not be graded on, but you should do it anyway.

Send me email. My address is `<aspnes@cs.yale.edu>`. In your message, include:

- Your name.
- Your status: whether you are an undergraduate, grad student, auditor, etc.
Whether you have ever taken a class that used Grade-o-Matic before.

^{1}- Anything else you'd like to say.

Optional: Create an account for yourself on PineWiki, the system that holds the course web pages, by following the UserPreferences link and filling in the form it sends you to. Use the subscription feature to get minute-by-minute spam about page changes (such as updates to this assignment). Say hello to everybody on the CS365/Discuss page.

# 2. Technical part

This part you will be graded on.

## 2.1. Asymptotic notation tricks

Show that all of the following statements hold:

- For all f, Theta(f(n)) is equal to the intersection of O(f(n)) and Omega(f(n)).
Every polynomial a

_{k}n^{k}+ a_{k-1}n^{k-1}+ ... + a_{0}with a_{k}> 0 and a_{i}>= 0 for i < k belongs to Theta(n^{k}).The function n

^{a}is in o(n^{b}) for any a < b.The function ln

^{a}n is in o(n^{b}) for any a and any b > 0.*Hint added after homework was distributed: The notation ln*^{a}n means (ln n)^{a}and not the logarithm of n to the base a. The logarithm of n to base a is written log_{a}n.If f(n) is in O(r(n)) and g(n) is in O(s(n)), where f(n), g(n), r(n), and s(n) are all non-negative for all n >= 0, then f(n)g(n) is in O(r(n)s(n)).

*The original version of this problem specificed only that r(n) and g(n) were non-negative, which was (a) almost certainly the result of a typo, and (b) not enough to prove the result if you use the definition of O() that doesn't include absolute values.*

## 2.2. Sums

Do Exercise 2.3.1 from page 67 of LevitinBook.

Do Exercise 2.3.4 from page 68 of LevitinBook.

Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)