Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'context': 0.05; 'say,': 0.05; 'chunk': 0.07; 'indexing': 0.07; 'variables.': 0.07; '"a"': 0.09; 'notation': 0.09; 'occasionally': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'worse': 0.09; 'aug': 0.13; 'amortized': 0.16; 'reasonably': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'recognizing': 0.16; 'subject:Big': 0.16; 'string': 0.17; 'wrote:': 0.17; 'saying': 0.18; 'variable': 0.20; 'changes': 0.20; 'constant': 0.22; 'statement': 0.23; 'paul': 0.24; 'header:In-Reply-To:1': 0.25; 'header:User-Agent:1': 0.26; 'charset:iso-8859-15': 0.26; 'guess': 0.27; 'fixed': 0.28; 'header:X-Complaints-To:1': 0.28; '-0700,': 0.29; 'behaviour': 0.29; "d'aprano": 0.29; 'steven': 0.29; 'writes:': 0.29; 'becomes': 0.30; 'e.g.': 0.30; 'point': 0.31; '(and': 0.32; 'to:addr:python-list': 0.33; 'typically': 0.33; 'text.': 0.35; 'expected': 0.35; 'sometimes': 0.35; 'there': 0.35; 'received:org': 0.36; 'but': 0.36; 'subject:: ': 0.38; 'some': 0.38; 'to:addr:python.org': 0.39; 'skip:" 10': 0.40; 'header:Received:5': 0.40; 'relatively': 0.62; 'talking': 0.66; 'upper': 0.75; 'complexity': 0.84; 'oscar': 0.84; 'subject:Abuse': 0.84 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Oscar Benjamin Subject: Re: Abuse of Big Oh notation Date: Mon, 20 Aug 2012 09:24:33 +0100 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> Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 8bit X-Gmane-NNTP-Posting-Host: cpc22-aztw25-2-0-cust431.aztw.cable.virginmedia.com In-Reply-To: <7xwr0ua1pw.fsf@ruckus.brouhaha.com> User-Agent: Groundhog Newsreader for Android X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 30 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1345451405 news.xs4all.nl 6947 [2001:888:2000:d::a6]:41283 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:27477 On Sun, 19 Aug 2012 16:42:03 -0700, Paul Rubin wrote: > Steven D'Aprano writes: > > Of course *if* k is constant, O(k) is constant too, but k is not > > constant. In context we are talking about string indexing and slicing. > > There is no value of k, say, k = 2, for which you can say "People will > > sometimes ask for string[2] but never ask for string[3]". That is absurd. > The context was parsing, e.g. recognizing a token like "a" or "foo" in a > human-written chunk of text. Occasionally it might be "sesquipidalian" > or some even worse outlier, but one can reasonably put a fixed and > relatively small upper bound on the expected value of k. That makes the > amortized complexity O(1), I think. No it doen't. It is still O(k). The point of big O notation is to understand the asymptotic behaviour of one variable as it becomes large because of changes in other variables. If k is small then you can often guess that O(k) is small. To say that an operation is O(k), however, is a statement about what happens when k is big (and is not refuted by saying that k is typically not big). Oscar