1. Bureaucratic part
This part you will not be graded on, but you should do it anyway.
Send me email. My address is <firstname.lastname@example.org>. 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 aknk + ak-1nk-1 + ... + a0 with ak > 0 and ai >= 0 for i < k belongs to Theta(nk).
The function na is in o(nb) for any a < b.
The function lna n is in o(nb) for any a and any b > 0. Hint added after homework was distributed: The notation lna n means (ln n)a and not the logarithm of n to the base a. The logarithm of n to base a is written loga 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.
Ulterior motive: The information in your email will be used to create an account for you in Grade-o-Matic. (1)