On Fri, Jan 28, 2005 at 08:16:59PM +0100, Henning Thielemann wrote:
But what do you mean with 1/O(n^2) ? O(f) is defined as the set of functions bounded to the upper by f. So 1/O(f) has no meaning at the first glance. I could interpret it as lifting (1/) to (\f x -> 1 / f x) (i.e. lifting from scalar reciprocal to the reciprocal of a function) and then as lifting from a reciprocal of a function to the reciprocal of each function of a set. Do you mean that?
On Thu, Feb 03, 2005 at 08:16:49PM -0500, Dylan Thurston wrote:
I think this is the only reasonable generalization from the established usage of, e.g., 2^(O(n)). In practice, this means that 1/O(n^2) is the set of functions asymptotically bounded below by 1/kn^2 for some k.
Careful, 2^x is monotone increasing; 1/x is monotone decreasing. I said 1/O(n^2) is Omega(1/n^2) for a good reason. Inequalities are reversed by monotone decreasing functions. Likewise, sech(O(n^2)) = Omega(sech(n^2)), which is happily immune to the effects of sign. Usually f(n) = O(g(n)) is done as there exist N, K so that |f(n)| <= K*|g(n)| for all n > N so e.g. e^x \in O((-1)^{\chi_\mathbb{Q}}\cdot e^x) etc. Also, you're in a bit of trouble wrt. 2^(O(n)). O(2^n) is something rather different. O(2^n) has |f(n)| <= K*|2^n| but 2^(O(n)) is 2^|f(n)| where |f(n)| <= K*|n|. If K >= 1/log(2) is sharp then then we have 2^|f(n)| >= e^|n| \in omega(2^n). -- wli