Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #93331

Re: Linear time baseconversion

References (5 earlier) <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 2015-06-30 09:29 -0600
Subject Re: Linear time baseconversion
Newsgroups comp.lang.python
Message-ID <mailman.189.1435678221.3674.python-list@python.org> (permalink)

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 15:39 -0700
  Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 16:56 -0600
  Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-29 17:10 -0600
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 16:23 -0700
    Re: Linear time baseconversion Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-06-30 01:09 +0100
      Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 01:52 -0700
        Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-06-30 11:07 +0200
          Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:20 -0700
          Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:34 -0700
            Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 02:43 -0700
              Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 06:22 -0700
                Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 07:13 -0700
                Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:29 -0600
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:45 -0600
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 09:40 -0600
            Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:22 +0200
          Re: Linear time baseconversion Chris Angelico <rosuav@gmail.com> - 2015-07-01 02:10 +1000
          Re: Linear time baseconversion Ian Kelly <ian.g.kelly@gmail.com> - 2015-06-30 10:34 -0600
            Re: Linear time baseconversion Christian Gollwitzer <auriocus@gmx.de> - 2015-07-01 00:27 +0200
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-29 23:49 -0700
  Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 10:12 -0600
    Re: Linear time baseconversion jonas.thornvall@gmail.com - 2015-06-30 09:24 -0700
      Re: Linear time baseconversion Michael Torrie <torriem@gmail.com> - 2015-06-30 13:55 -0600

csiph-web