On Wed, 15 Feb 2012 19:20:21 +0100, Franck Ditter wrote:
> What is the cost of calling primes(n) below ? I'm mainly interested in
> knowing if the call to append is O(1)
Your primes() function appears to be a variation on trial division, which
is asymptotically O(n*sqrt(n)/(log n)**2). Regardles
On Wed, Feb 15, 2012 at 1:28 PM, Dennis Lee Bieber
wrote:
> On Wed, 15 Feb 2012 11:11:27 -0800, Chris Rebert
> wrote:
>
>
>>"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
>> -- list_resize()
>>
> Rather perverse, is it not? The first set is plain doubling, but
> then yo
On 2/15/2012 2:11 PM, Chris Rebert wrote:
It's slightly more complex:
http://hg.python.org/cpython/file/096b31e0f8ea/Objects/listobject.c
"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
-- list_resize()
This has apparently changed from time to time.
--
Terry Jan Reedy
-
On Wed, Feb 15, 2012 at 10:43 AM, Ian Kelly wrote:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
>
> I believe the behavior in CPython is that if the array
Ian Kelly, 15.02.2012 19:43:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
>
> I believe the behavior in CPython is that if the array is full, the
> capacity
On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
> What is the cost of calling primes(n) below ? I'm mainly interested in
> knowing if the call to append is O(1), even amortized.
Yes, it's amortized O(1). See:
http://wiki.python.org/moin/TimeComplexity
>From a relatively shallow analysis
On 02/15/2012 01:20 PM, Franck Ditter wrote:
What is the cost of calling primes(n) below ? I'm mainly interested in
knowing if the call to append is O(1), even amortized.
Do lists in Python 3 behave like ArrayList in Java (if the capacity
is full, then the array grows by more than 1 element) ?
d
On Wed, Feb 15, 2012 at 10:20 AM, Franck Ditter wrote:
> What is the cost of calling primes(n) below ? I'm mainly interested in
> knowing if the call to append is O(1), even amortized.
> Do lists in Python 3 behave like ArrayList in Java (if the capacity
> is full, then the array grows by more tha
What is the cost of calling primes(n) below ? I'm mainly interested in
knowing if the call to append is O(1), even amortized.
Do lists in Python 3 behave like ArrayList in Java (if the capacity
is full, then the array grows by more than 1 element) ?
def sdiv(n) : # n >= 2
"""returns the sm
