Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos Newsgroups: comp.programming Subject: Re: on expressing o() in terms of O(), Omega() or Theta() Date: Tue, 21 Mar 2017 08:17:11 -0300 Organization: Aioe.org NNTP Server Lines: 108 Message-ID: <86shm6j2vc.fsf@toledo.com> References: <86var4n9nc.fsf@toledo.com> <20170319200229.778@kylheku.com> <86pohbn5yp.fsf@toledo.com> <20170320120639.205@kylheku.com> NNTP-Posting-Host: BuEqJTf8bEmpZhBIUMG+Zw.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain X-Complaints-To: abuse@aioe.org User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt) X-Notice: Filtered by postfilter v. 0.8.2 Cancel-Lock: sha1:r6Y7zX2hhbeGLLNfuWwwNBuoYLU= Xref: csiph.com comp.programming:7594 Kaz Kylheku <336-986-7787@kylheku.com> writes: > On 2017-03-20, Daniel Bastos wrote: >> Kaz Kylheku <336-986-7787@kylheku.com> writes: >> >>> On 2017-03-19, Daniel Bastos wrote: >>>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or >>>> any combination of them? >>> >>> To warm up, first define <= and >= in terms of =. >> >> I don't think that's very easy to do. > > That depends. We can define 'x = a' in terms of 'x <= a' and 'x >= a' > very easily like this: > > x = a <==iff===> x <= a and x >= a Sure. That's different from defining <= and >= in terms of =. > This reasoning over to the big Oh family which are defined using > inequalities. Suppose we use the Knuth definition of Omega, which > is the inverse of big Oh: > > f is O(g) <==> g is Omega(f) > > If both are true, then, I think: f is Theta(g): > > f = Theta(g) iff f = O(g) and g = Omega(f) > > If f grows no faster than g, but also at least as fast as g, then it > grows exactly as fast as g! What's left is to show that using the > expanded definition of what these notations mean: the quantified > expressions over inequalities. The definition of Theta involves the > binding of two constants under existential quantifiers, and asserting > that one function is sandwiched between these two constant factors of > the other, for sufficiently large values of the independent variable. > > Now about o in terms of Theta and the others: which little o definition > are you using? I think the same as yours. Def. We say f in o(g) if there exists a natural number n(0) > 0 such that 0 <= f < c g for any n >= n(0) and for all c > 0, c being a real number. > The problem is that the definitions of big and little O are very > similar. There is a hair-splitting difference which shows up as in one > logical quantifier being universal in little Oh whereas it is > existential in big Oh. f = o(g) asserts that there is a sufficiently > large value of the independent variable x such that for all positive > constants C, |f(x)| <= C|g(x)|. Whereas big O only asserts that this > is true for some sufficiently large, positive constant C, not for all > positive constants C. > > Basically, you have to work with the expanded versions of these > definitions and see if or how you can work one in terms of the others. > > Is there some logical combination of several of them which will > derive the one you want (using whatever manipulation is necessary: > reshuffling the quantifiers, etc). I do have reshuffling the quantifiers in mind. I know 4 theorems about reshuffling quantifiers. 1. For any x, P(x) iff not exists x such that ~P(x). 2. Exists x, P(x) iff not for all x such that ~P(x). 3. For any x, ~P(x) iff not exists x such that P(x). 4. Exists x, ~P(x) iff not for any x such that P(x). (Using both ~ and ``not'' as negation to ease reading and writing.) Looking at my definition of o(), I could rewrite it as: for any c > 0 (for any n > n(0), P(c,f,g)) which is equivalent to there is no c such that ~(for any n > n(0), P(c,f,g)) which is equivalent to there is no c such that some n > n(0) satifies ~P(c,f,g). Expanding ~P(), we get ~P(c,f,g) iff 0 > f >= c g. Therefore the definition of o() says that no suitable c exists such that some index n > n(0) satisfies c g <= f < 0. (Equation 1.) That's obviously true as c, g and f are all positive constant and functions, respectively. Nevertheless, the point of my investigation is to see if I can somehow introduce Omega(), O() or Theta() in places of these statements. The definition of Omega() uses ``c g <= f'', hence perhaps I can write f in o(g) iff no c exists such that f in Omega(g) for some n > n(0). I'm worried about the ``< 0'' in Equation 1. I'm very confused at this point. I don't know if what I just did is correct and whether it takes anywhere interesting. (I did mange to introduce Omega, though. That illuminates things a bit.) Thank you.