Asymptotics

Assignment

Problems from Mathematics for Computer Science (MCS).

Note: for each question, give an explanation of why the answer is what it is. This does not need to be a formal proof. When possible you can use my big-O rules of thumb: (0) ignore constants multiplied out front, (1) for terms that are added just keep the fastest growing one (fastest eventually), (2) n^c grows faster than (log(n))^d for any c > 0, (3) (1+c)^nd grows faster than n^e for any c > 0 and d > 0.

1. MCS Problem 14.20. Indicate whether each statement is true or not. Explain why for each.
   Note that for functions f(n) and g(n), the notation "f ~ g" means that the limit of f(n)/g(n) approaches 1 as n goes to infinity (this is like them being Theta of each other with a constant factor of 1); equivalently, for any constant epsilon>0 you can find a value n0 such that (1-epsilon) g(n) <= f(n) <= (1+epsilon g(n) for all n >= n0.
   Note that sin(x) ranges between -1 and 1, and periodically goes between those two values forever; that is all you need to know about sin(x) for the one that has sin in the formula.
2. MCS Problem 14.21. Show an asymptotic equation pertaining to factorial, using Stirling's formula.
3. MCS Problem 14.26. Arrange the functions in increasing big-O order. For some of these you also need to pay attention to the precise definition of big O.
4. MCS Problem 14.28. Determine which of the given options describes each function's asymptotic behavior. For part (e) you will need one of the summation formulas from here: https://en.wikipedia.org/wiki/Summation#Summation_index_in_exponents
5. MCS Problem 14.33. For each pair of functions, find constants c and n0 that make the asymptotic formula true. The book asks for the smallest c, but you can find any c that satisfies the definitions. For each one, give some justification as well.

Old assignment, from last term

1. MCS Problem 14.18. Find the least non-negative integer n to make each statement true. Note that n=0 is theoretically a possible answer for some of these.
2. MCS Problem 14.19. For each cell in the table, indicate whether the asymptotic statement is true or not. Note that for the ones that have sin, you have to pay attention to the precise definition of big O. For the one with n! you can use Sterling's approximation (any of the variations will be good enough).
3. MCS Problem 14.25. Indicate which cells in the table are true. Note that for functions f(n) and g(n), the notation "f ~ g" means that the limit of f(n)/g(n) approaches 1 as n goes to infinity (this is like them being Theta of each other with a constant factor of 1). For the one with n! you can use Sterling's approximation.
4. MCS Problem 14.26. Arrange the functions in increasing big-O order. For some of these you also need to pay attention to the precise definition of big O.
5. MCS Problem 14.34. False claim, identify where it is incorrect.