Difference between revisions of "Asymptotics"
(Created page with "=Assignment= Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS). # MCS Problem 14.18 # MCS Problem 14.19 # MCS Proble...") |
|||
| Line 2: | Line 2: | ||
Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS). | Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS). | ||
| − | # MCS Problem 14.18 | + | # MCS Problem 14.18. Note that n=0 is theoretically a possible answer for some of these. |
| − | # MCS Problem 14.19 | + | # MCS Problem 14.19. 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). |
| − | + | # MCS Problem 14.25. 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. | |
| − | # MCS Problem 14.25 | + | # MCS Problem 14.26. For some of these you also need to pay attention to the precise definition of big O. |
| − | # MCS Problem 14.26 | + | # MCS Problem 14.34. |
| − | # MCS Problem 14.34 | ||
Revision as of 11:48, 18 November 2022
Assignment
Problems from Mathematics for Computer Science (MCS).
- MCS Problem 14.18. Note that n=0 is theoretically a possible answer for some of these.
- MCS Problem 14.19. 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).
- MCS Problem 14.25. 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.
- MCS Problem 14.26. For some of these you also need to pay attention to the precise definition of big O.
- MCS Problem 14.34.
