Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!news-out.octanews.net!indigo.octanews.net!auth.beige.octanews.com.POSTED!not-for-mail From: Paul Rubin Newsgroups: comp.lang.python Subject: Re: Abuse of Big Oh notation References: <308df2af-abe7-4043-b199-0a39f440e0ab@googlegroups.com> <502f8a2a$0$29978$c3e8da3$5496439d@news.astraweb.com> <7xehn4vyya.fsf@ruckus.brouhaha.com> <5030832d$0$29978$c3e8da3$5496439d@news.astraweb.com> <7x8vdbmho6.fsf@ruckus.brouhaha.com> <7xfw7ilqnd.fsf@ruckus.brouhaha.com> <50314968$0$29978$c3e8da3$5496439d@news.astraweb.com> <7xwr0ua1pw.fsf@ruckus.brouhaha.com> <7xr4r1pn72.fsf@ruckus.brouhaha.com> Date: Mon, 20 Aug 2012 12:29:12 -0700 Message-ID: <7xfw7hl5vb.fsf@ruckus.brouhaha.com> Organization: Nightsong/Fort GNOX User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) Cancel-Lock: sha1:zypz1jFsPaVFUM8np9kzOoZxp+g= MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Lines: 17 NNTP-Posting-Date: 20 Aug 2012 14:29:12 CDT X-Complaints-To: abuse@octanews.net Xref: csiph.com comp.lang.python:27527 Ian Kelly writes: > The difference between the two is that the former is bounded by a > constant that is fundamental to the algorithm at hand,... S is > clearly bounded by the constraints of actual shoes, so we can safely > treat S as a constant and call it O(N). Thanks, that is a good explain of what I was trying to get at. One quibble is in the parsing example, the constant is inherent in the distribution of input data one expects to normally encounter, rather than in the algorithm itself. It's sort of like saying dictionary access (based on hashing) is O(1), based on the variety of input data that is normally used. There is such a thing as pathological (e.g. malicious) input data that causes a lot of hash collisions, making O(n) access in the size of the dictionary. I suppose abnormal input should also be taken into account in examples involving parsing if one parses potentially hostile data.