Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by randartie | Hacker News Reader

Full thread

randartie·

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

View on HN

Of course "not obvious" is subjective, but I offer this example: f = log n! and g = n log n.

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...

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).

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.

Depends what you consider to be obvious, I guess...

Such as f(x)=2x and g(x)=3x perhaps?

Another common one might be f(x)=log₂ x and g(x)=logₑ 10x

Big O f log, where is the factors don't count and the subscripts don't matter.

Reply on news.ycombinator.com