4 ms·

Question 1 is interesting. Are there any 'not obvious' examples of functions f and g such that O(f(n)) == O(g(n))?

• capisce 14y ago
  Such as f(x)=2x and g(x)=3x perhaps?
  • sesqu 14y ago
    Another common one might be f(x)=log₂ x and g(x)=logₑ 10x
    • Evbn 14y ago
      Big O f log, where is the factors don't count and the subscripts don't matter.
• cperciva 14y ago
  Depends what you consider to be obvious, I guess...
• shrughes 14y ago
  Consider a program that solves the traveling salesman problem in the following fashion. It searches for an algorithm that solves the traveling salesman problem and proof that such an algorithm runs in polynomial time, and then uses said algorithm to find a solution for the input, simultaneously while trying to solve the traveling salesman problem with some non-polynomial time algorithm that takes O(g(n)) time. Let f(n) be the worst case running time that program has on inputs of size n. Whether O(f(n)) = O(g(n)) is not obvious. Edit: Actually you asked for an example, and I'm not sure I gave one.
• nandemo 14y ago
  Of course "not obvious" is subjective, but I offer this example: f = log n! and g = n log n.
  • mdkess 14y ago
    Is 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 ago
      Informally, 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).