Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.062
X-Spam-Evidence: '*H*': 0.88; '*S*': 0.00; 'linear': 0.07; 'subject:skip:b 10': 0.07; 'calculating': 0.09; 'sake': 0.09; 'algorithm': 0.13; 'times,': 0.13; 'dig': 0.16; 'growth.': 0.16; 'linear,': 0.16; 'quadratic': 0.16; 'wrote:': 0.16; "wouldn't": 0.16; 'input': 0.18; 'constant': 0.22; 'am,': 0.23; 'code,': 0.23; '2015': 0.23; 'header:In-Reply-To:1': 0.24; 'message- id:@mail.gmail.com': 0.28; "i'm": 0.29; 'factor': 0.29; 'lines': 0.30; 'subject:time': 0.31; 'maybe': 0.31; 'doubt': 0.33; 'me?': 0.34; 'received:google.com': 0.34; 'to:addr:python-list': 0.35; 'being': 0.36; '(i.e.': 0.36; 'subject:: ': 0.37; 'tue,': 0.38; 'does': 0.39; 'to:addr:python.org': 0.39; 'seem': 0.39; 'increased': 0.61; 'become': 0.62; 'matter': 0.63; '30,': 0.63; '500': 0.63; 'results': 0.66; 'analysis': 0.70; 'algorithm,': 0.84; 'complexity': 0.84; 'estimation': 0.84; 'proving': 0.84; 'taken.': 0.84; 'to:name:python': 0.84; 'doubling': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=DUezcHBp1lBqTKU3JnJDMM3wt5WVVihgqj2uDs7quA4=; b=PnvB9Tsn136/O74fD9PlCMNqA2PT6HYdAEoDGNpFC1JLqN2mm6NpdSoA0fAIiXhnTG j8WV0nShlUUiInBM4e6RkPXcOtnj+h5tYxu2nAcs8Qe58TOCuosqi/j5pKR8v4UUNAgr Tl48Y1q+2Fng1VgEjpPjZjKlYXt7s4QTJmA3rIl48iW0j2dpRoRYG+p9kxCTu5TLLOIO BrA0O63ntNWnpuXnUsvaQ1WP/9TRlQBv1f9JFkG1QizbzDaNoWWmB0ZOJjJedNSCUIaE tyGD7qCFE7gQoOtb9pyAP6WEUo8p5hglWd5PwyJIwI4w5o6hsDrh18jS/H+EqF7nIPLi 1eQg==
X-Received: by 10.13.251.199 with SMTP id l190mr26640594ywf.148.1435678218926; Tue, 30 Jun 2015 08:30:18 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <84ac9885-f0f2-47fb-92bc-a856ede6d818@googlegroups.com>
References: <777831f0-d4b4-48f6-ae0b-c9b1ea7ffc06@googlegroups.com> <CALwzidms2BGRjHCuLB5_uszbx9Q-rdtOob_LGHQoO3K3ZD=Q7Q@mail.gmail.com> <mailman.175.1435619500.3674.python-list@python.org> <87r3ouawgt.fsf@bsb.me.uk> <7c6dac9d-5722-4179-bd7e-ceaac6698490@googlegroups.com> <mmtm6k$8b7$1@dont-email.me> <c92c3dc9-8a00-4244-bbd7-383f34983935@googlegroups.com> <0439e7f6-2604-4a07-802b-81ea03782f62@googlegroups.com> <332f7cc7-4cc7-469f-a1c3-cbba40b7b641@googlegroups.com> <84ac9885-f0f2-47fb-92bc-a856ede6d818@googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 30 Jun 2015 09:29:39 -0600
Subject: Re: Linear time baseconversion
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20+
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.189.1435678221.3674.python-list@python.org>
Lines: 20
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1435678221 news.xs4all.nl 2875 [2001:888:2000:d::a6]:53065
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:93331

On Tue, Jun 30, 2015 at 8:13 AM,  <jonas.thornvall@gmail.com> wrote:
>> Regarding the time it seem to double the digits quadruple the time. And that is still linear or?
>
> 2x seem linear to me?

That's not linear, nor is it "2x". If doubling the size of the input
quadruples the time, then doubling the size of the input twice (i.e.
quadrupling the size of the input) results in the time being increased
by a factor of 16. Double it three times, and the time taken is
increased by a factor of 64. That's quadratic behavior.

If the algorithm were actually linear, then a constant factor of "2x"
wouldn't matter when calculating the growth. Doubling the size of the
input would simply double the time taken.

Of course, this is just an empirical estimation of the asymptotic
complexity of the algorithm, not a proof. Maybe after 10,000 digits it
actually does become linear, although I doubt it. Proving it would
require analysis of the code, and I'm not willing to dig into 500
lines of Javascript just for the sake of it.