3 ms·
Of course "not obvious" is subjective, but I offer this example: f = log n! and g = n log n.
by nandemo 14y ago
Of course "not obvious" is subjective, but I offer this example: f = log n! and g = n log n.
- mdkess 14y agoIs this true (by the definition on the site)? I mean, certainly O(log(n!)) <= O(n log n) since we can just say that log(n!) = log(n) + log(n-1) + ... + log(1) <= log(n) + log(n) + ... + log(n) = n * log(n), but is the bound tight? It's been too long. EDIT: Answering my own question... yes. http://www.cs.sfu.ca/CourseCentral/307/jmanuch/lec/factorial.pdf http://www.cs.sfu.ca/CourseCentral/307/jmanuch/lec/factorial...
- Evbn 14y agoInformally, the left side is he integral of log over 1 to n, which is equal to n log(n) - n plus bounded error, which asymptotically is n log(n).