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 18:09:26 GMT Organization: None Lines: 49 Message-ID: References: <25bf7834-1bb1-4702-9e18-0bd691958ec8@googlegroups.com> X-Trace: individual.net Y2KKEnbSaHbJefq3o2Q4fwuT7+d2Xp9mBT6VMaVhlR2kRDjtpw X-Orig-Path: not-for-mail Cancel-Lock: sha1:W99JOZBiIKNIf4IgCu1j9OS7mss= X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Xref: csiph.com comp.programming:3739 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. > It is quite possible for a O(2^n) algorithm to be much faster than a > O(log n) algorithm for small n, primarily because the purpose of the O() > notation is to look at scaling at large values of n. But this part I agree with! > When determining the O() value for an algorithm, you look at how much of > something (time, memory, or what ever) the algorithm uses as n > increases. At some point, the amount of that stuff that an O(x(n)) > algorithm uses will be approximately k*x(n) for all n sufficiently > large. We ignore the k factor, as that becomes a function of the units > we are using, and as long as k is "reasonable" it doesn't normally > affect our decisions as to which algorithm to use. There can be cases > though, where n doesn't really get extremely large, where the the scale > factor may make a "larger" O() be better than the lower O(), or you need > to look at "smaller" growth terms as they have a significant scale > factor and there contribution isn't negligible. To the OP: I don't have a specific book or other resource to recommend, but a search term that may be useful is "analysis of algorithms". -- B. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor.