Hacker Newsnew | past | comments | ask | show | jobs | submit | gargleblaster's commentslogin

I think that question 1 is not well formulated (unless that is the answer he expects). Equality makes only very limited sense for asymptotic notation.


It is perfectly well formulated. The notation O(f(n)) denotes a set of functions. The question is asking if the two sets O(2^n) and O(3^n) are the same set.


That's right. Some people get confused due to the rather unfortunate convention of writing f(n) = O(n) instead of the correct f(n) ∈ O(n).


I think the OP is looking for a bit more of an answer than a simple Yes/No.


He is also asking "Why?", i.e., for a proof[1] to back up your Yes/No answer. Seems like a perfectly good question.

[1] Calculation, if you prefer.


It's a perfectly sensible question. Knowing that both O(2^n) and O(3^n) are sets, and using the definition of set equality, it asks whether "f in O(2^n)" implies "f in O(3^n)", and vice versa. Only one of the implications holds...


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: