Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: blmblm@myrealbox.com Newsgroups: comp.programming Subject: Re: algorithm analysis Big-O Date: 15 Sep 2013 20:42:30 GMT Organization: None Lines: 81 Message-ID: References: <25bf7834-1bb1-4702-9e18-0bd691958ec8@googlegroups.com> <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk> X-Trace: individual.net qas07CSLL09CM8muabRh4Ag0Qyjn2JuGwAnIDb/QZ+rbitoHmF X-Orig-Path: not-for-mail Cancel-Lock: sha1:k73UdKVZRzm8JvK+SkVpLuXogic= X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Xref: csiph.com comp.programming:3741 In article <0.d8dc0418ebeb284bcb69.20130915204724BST.87ioy1uasz.fsf@bsb.me.uk>, Ben Bacarisse wrote: > blmblm@myrealbox.com writes: > > > In article , > > Richard Damon wrote: > >> On 9/14/13 9:32 AM, gdotone@gmail.com wrote: > >> > O(log n) < O(n) < O(nLog n) < O(n^2) < O(n^3) < O(2^n) in running time. > >> > >> Only for n large. > > > > Isn't that part of the def .... Oh. Well, maybe not exactly: > > The formal definition of what it means for a function to be O(f(n)) > > does include a notion of "for sufficiently large n", but I'm not > > finding, in a quick Web search, a formal definition of what > > "O(f(n)) < O(g(n))" means. But I'm inclined to think that it's > > something along the lines of "if function f1(n) is O(f(n)), and > > function g1(n) is O(g(n)), then for sufficiently large n, > > f1(n) < g1(n)". Maybe someone who knows this off the top of > > his/her head, or has the right books nearby, can fill in the > > details. > > With that meaning, neither O(1) < O(n) nor O(n) < O(1) would be true, so > if that is what was meant, it's not very useful. The problem here is > that if f is O(1) it is also O(n). Indeed. What was I thinking .... (*WAS* I thinking .... ) > That there is some confusion here is not surprising. The exact meaning > of operators near a "big O" is often hard to determine. For example, > some people write "g = O(f)", but whatever the "=" means, it certainly > isn't equality. In other fields you'll see it "added": > > p(x) = x^5 + a.x^4 + O(x^2). > > Again, that can't be normal addition. > > One approach to formalising it is to say that O(f) is the set of all > functions, g, that have the property that |g(n)| < C.f(n) for some > constant C and all but a finite set of n. (There are other ways to get > similar meanings -- there doesn't seem to be a universal definition.) > > With this definition, O(f) is a real "thing" (just a set) and we can use > normal set operations on it. For example, where many people write, > informally, "g = O(f)", we can now write "g in O(f)" using set > membership. With this more formal definition, using less than > (especially in ASCII) as the subset relation is not unreasonable. With > this meaning, O(n) < O(n^2) because all functions that are in O(n) are > also in O(n^2), whilst there are functions in O(n^2) that are not in > O(n). (I'd use a Unicode "subset of" if that were not likely to derail > the thread with a discussion of non-ASCII postings.) > > I like this approach, but it's not universal and it may even be a > minority view. Some authors just think of O(f) as a shorthand for a > property (pronounced "order of f") and, if they are careful, they write > "g is O(f)". If they are not so careful and write "g = O(f)" the "=" is > meant to be pronounced "is". In this sort of informal context, I'd > guess that O(f) < O(g) means that all functions that are O(f) are also > O(g), and that there exists at least one function that is O(g) that is > not O(f). However, this is derived from what I *want* it to mean, > rather than any guess at what the OP meant. > > In complexity theory there are lots of sets of things with interesting > properties (decidable languages, P, NP and so on), so I think it makes > perfect sense to formalise O(f) as just another set of things with some > interesting property. > "Couldn't snip a word" ? Thanks -- this is pretty much the meaning I think I would have had in mind if I'd been thinking clearly. :-)?? I like your set-based definition, but defining O(f(n)) as a property seems plausible too (and then you could convey the "<" idea using implication? i.e., if a function has property O(f(n) it also has property O(g(n))?). -- B. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor.