Re: How to take in a string of any size?

From: Jarno A Wuolijoki (jwuolijo_at_cs.Helsinki.FI)
Date: 08/24/04 

Date: Tue, 24 Aug 2004 02:39:45 +0300

On Mon, 23 Aug 2004, josh wrote:

> SM Ryan wrote:
>
> > # Notice that each time you allocated memory you ask for twice the
> > # amount of memory that you have already used. The only real
> > # benefit that I can see to repeated realloc calls is if the goal
> >
> > There's a minor benefit of that it makes the algorithm O(n) instead
> > of O(n^2).
>
> makes it O(n log n) instead of O(n^2)
>
> Counting and seeking back to the start would be O(n) (even if seeking itself
> is O(n)), as would using some sort of linked structure to store the string.

I haven't followed this thread from the start but is it by any
chance about reallocing in the pattern 1, 2, 4, 8 etc?

If so, at the end you have performed log N calls to realloc
which, if their execution time is linear to the amount of bytes
allocated, consume k*(1+2+4+8+...+2^ceil(log(N))) < 4*k*N time.

Relevant Pages

  • Re: Can this be written more concisely in a functional style
    ... > conciseness of. ... I think that in seeking to make it more concise, ... If you want to hide the algorithm, do so inside a helper function. ... explicit semantics where the algorithm is implemented. ...
    (comp.lang.python)
  • Re: Apple was created on the cheap...
    ... Alan Baker wrote: ... doesn't change the fact that I was seeking examples of what *I* had said that didn't express agreement with *my* position in this thread. ... Josh ...
    (comp.sys.mac.advocacy)
  • Estimating the condition of an upper triangular matrix
    ... algorithm to estimate the condition (i.e. the ratio of the largest and ...
    (sci.math.num-analysis)
  • Re: Essay on PID Motor control
    ... I still did not get the basic information I'm seeking, to wit: ... > 1) Is the algorithm as published not the same as the one tested? ...
    (comp.robotics.misc)
  • Re: main connective in SL
    ... Enderton) wrote: ... >> what's the main connective in these two logic strings, ... > Perhaps you are seeking an algorithm that counts the left and ...
    (sci.logic)