Filling 2d array in less than O(n^2) time

Discussion in 'C++' started by pjhyett@gmail.com, Nov 18, 2005.

  1. Guest

    standard 2d array filling with increasing numbers for rows and columns:

    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    a[j] = i + j;

    problem is it's O(n^2). I'm looking for a method to decrease the time,
    any suggestions? I'm googling for dynamic programming solutions, but
    not coming up with much.
     
    , Nov 18, 2005
    #1
    1. Advertising

  2. red floyd Guest

    wrote:
    > standard 2d array filling with increasing numbers for rows and columns:
    >
    > for(int i=0;i<n;i++)
    > for(int j=0;j<n;j++)
    > a[j] = i + j;
    >
    > problem is it's O(n^2). I'm looking for a method to decrease the time,
    > any suggestions? I'm googling for dynamic programming solutions, but
    > not coming up with much.
    >


    I don't think it's possible, since you *must* assign n^2 elements.
     
    red floyd, Nov 18, 2005
    #2
    1. Advertising

  3. rwf_20 Guest

    red floyd wrote:
    > wrote:
    > > standard 2d array filling with increasing numbers for rows and columns:
    > >
    > > for(int i=0;i<n;i++)
    > > for(int j=0;j<n;j++)
    > > a[j] = i + j;
    > >
    > > problem is it's O(n^2). I'm looking for a method to decrease the time,
    > > any suggestions? I'm googling for dynamic programming solutions, but
    > > not coming up with much.
    > >

    >
    > I don't think it's possible, since you *must* assign n^2 elements.


    Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    (theoretically) as can be.

    Ryan
     
    rwf_20, Nov 18, 2005
    #3
  4. Markus Moll Guest

    Hi

    rwf_20 wrote:

    >
    > red floyd wrote:
    >> I don't think it's possible, since you *must* assign n^2 elements.

    >
    > Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    > (theoretically) as can be.


    Huh? Linear in what? If, as given in the example, n is to denote the number
    of columns and rows and you count the number of assignments, then of course
    there are exactly n^2 \in O(n^2) of them.

    Nevertheless it is obviously true that this is optimal.

    Markus
     
    Markus Moll, Nov 18, 2005
    #4
  5. red floyd Guest

    rwf_20 wrote:
    > red floyd wrote:
    >
    >> wrote:
    >>
    >>>standard 2d array filling with increasing numbers for rows and columns:
    >>>
    >>>for(int i=0;i<n;i++)
    >>> for(int j=0;j<n;j++)
    >>> a[j] = i + j;
    >>>
    >>>problem is it's O(n^2). I'm looking for a method to decrease the time,
    >>>any suggestions? I'm googling for dynamic programming solutions, but
    >>>not coming up with much.
    >>>

    >>
    >>I don't think it's possible, since you *must* assign n^2 elements.

    >
    >
    > Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    > (theoretically) as can be.


    Would you care to explain how it's O(n), and not O(n^2)?
     
    red floyd, Nov 18, 2005
    #5
  6. E. Mark Ping Guest

    In article <_7sff.15956$>,
    red floyd <> wrote:
    >rwf_20 wrote:
    >>
    >>
    >> Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    >> (theoretically) as can be.

    >
    >Would you care to explain how it's O(n), and not O(n^2)?


    Because 'n' typically represents the number of elements. There are
    are rows*columns elements. One operation per element. Hence O(n)
    where n is the number of elements in the array.
    --
    Mark Ping
     
    E. Mark Ping, Nov 18, 2005
    #6
  7. mlimber Guest

    wrote:
    > standard 2d array filling with increasing numbers for rows and columns:
    >
    > for(int i=0;i<n;i++)
    > for(int j=0;j<n;j++)
    > a[j] = i + j;
    >
    > problem is it's O(n^2). I'm looking for a method to decrease the time,
    > any suggestions? I'm googling for dynamic programming solutions, but
    > not coming up with much.


    Initialize it statically, and then it will be filled at load-time
    rather than run-time. At file/namespace scope, do this:

    int a[][] = { { 0, 1, 2, 3 }, { 4, 5, 6, 7 } };

    Of course this limits your flexibility.

    Cheers! --M
     
    mlimber, Nov 18, 2005
    #7
  8. Howard Guest

    "E. Mark Ping" <> wrote in message
    news:dlljok$1isk$...
    > In article <_7sff.15956$>,
    > red floyd <> wrote:
    >>rwf_20 wrote:
    >>>
    >>>
    >>> Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    >>> (theoretically) as can be.

    >>
    >>Would you care to explain how it's O(n), and not O(n^2)?

    >
    > Because 'n' typically represents the number of elements. There are
    > are rows*columns elements. One operation per element. Hence O(n)
    > where n is the number of elements in the array.
    > --


    There are not neccessarily any "elements" to speak of in the general case.

    And in this case, he's speaking of n as the size of both the rows and the
    columns, as you can see by the code. There are rows*columns operations, so
    that means n*n operations, which makes it O(n^2). The cost grows by the
    square of the value n.

    -Howard
     
    Howard, Nov 18, 2005
    #8
  9. Pete Becker Guest

    Howard wrote:

    > "E. Mark Ping" <> wrote in message
    > news:dlljok$1isk$...
    >
    >>In article <_7sff.15956$>,
    >>red floyd <> wrote:
    >>
    >>>rwf_20 wrote:
    >>>
    >>>>
    >>>>Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    >>>>(theoretically) as can be.
    >>>
    >>>Would you care to explain how it's O(n), and not O(n^2)?

    >>
    >>Because 'n' typically represents the number of elements. There are
    >>are rows*columns elements. One operation per element. Hence O(n)
    >>where n is the number of elements in the array.
    >>--

    >
    >
    > There are not neccessarily any "elements" to speak of in the general case.
    >


    Big-Oh notation refers to the depenency of the time complexity of an
    algorithm on the number of elements that it's applied to.

    > And in this case, he's speaking of n as the size of both the rows and the
    > columns, as you can see by the code. There are rows*columns operations, so
    > that means n*n operations, which makes it O(n^2). The cost grows by the
    > square of the value n.
    >


    The cost grows by the square of the value of n, but that's not the
    meaning of big-Oh notation.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, Nov 19, 2005
    #9
  10. Greg Comeau Guest

    In article <>,
    mlimber <> wrote:
    > int a[][] = { { 0, 1, 2, 3 }, { 4, 5, 6, 7 } };


    You can't have [][] like that even on a definition.
    Only the first dimension can be []'d
    --
    Greg Comeau / Celebrating 20 years of Comeauity!
    Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
    World Class Compilers: Breathtaking C++, Amazing C99, Fabulous C90.
    Comeau C/C++ with Dinkumware's Libraries... Have you tried it?
     
    Greg Comeau, Nov 19, 2005
    #10
  11. meagar Guest

    Even for very large arrays, the method you provide should only add a
    small fixed overhead to your program's initialization.

    If, however, you're continually modifying the array's values and then
    restoring it's initial state, you might consider using your method to
    initially populate the array, and then creating a copy to work on with
    memcpy. You could then restore the copy's state to the original values
    each time with a single call to memcpy. You'll use twice the memory,
    but it will be much faster then repeatedly using your nested for loops.
     
    meagar, Nov 20, 2005
    #11
  12. Howard Guest

    "Pete Becker" <> wrote in message
    news:...
    > Howard wrote:
    >
    >> "E. Mark Ping" <> wrote in message
    >> news:dlljok$1isk$...
    >>
    >>>In article <_7sff.15956$>,
    >>>red floyd <> wrote:
    >>>
    >>>>rwf_20 wrote:
    >>>>
    >>>>>
    >>>>>Yes, this algorithm is not O(n^2). It is O(n), and as efficient
    >>>>>(theoretically) as can be.
    >>>>
    >>>>Would you care to explain how it's O(n), and not O(n^2)?
    >>>
    >>>Because 'n' typically represents the number of elements. There are
    >>>are rows*columns elements. One operation per element. Hence O(n)
    >>>where n is the number of elements in the array.
    >>>--

    >>
    >>
    >> There are not neccessarily any "elements" to speak of in the general
    >> case.
    >>

    >
    > Big-Oh notation refers to the depenency of the time complexity of an
    > algorithm on the number of elements that it's applied to.
    >
    >> And in this case, he's speaking of n as the size of both the rows and the
    >> columns, as you can see by the code. There are rows*columns operations,
    >> so that means n*n operations, which makes it O(n^2). The cost grows by
    >> the square of the value n.
    >>

    >
    > The cost grows by the square of the value of n, but that's not the meaning
    > of big-Oh notation.
    >


    I was about to argue with you, given what seems obvious to me that the
    complexity (cost) increases by the square of the input variable. But I did
    some "Googling", and found that it does indeed seem to be the convention
    that for arrays, the fact that they have width and height is not relevant,
    but rather it is their total "size" that matters. Which makes sense, since
    it is the size that grows by the square of that "n" variable, not the
    computing cost, given that size.

    -Howard



    -Howard
     
    Howard, Nov 21, 2005
    #12
  13. Vladimir Guest

    meagar wrote:
    > memcpy. You could then restore the copy's state to the original values
    > each time with a single call to memcpy. You'll use twice the memory,
    > but it will be much faster then repeatedly using your nested for loops.


    The call to memcpy may be single, but extra reading from memory
    would make initialization quite slower in practice.

    --
    Vladimir
     
    Vladimir, Nov 22, 2005
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. falcon
    Replies:
    10
    Views:
    19,234
    Roedy Green
    Feb 24, 2006
  2. Graeter than or less than

    , Jun 21, 2007, in forum: ASP .Net
    Replies:
    4
    Views:
    886
    bruce barker
    Jun 21, 2007
  3. Ray Wood

    Time on Update is exactly 3 hours less than time entered

    Ray Wood, Jul 17, 2003, in forum: ASP .Net Web Services
    Replies:
    0
    Views:
    191
    Ray Wood
    Jul 17, 2003
  4. Mohsen Pahlevanzadeh
    Replies:
    0
    Views:
    146
    Mohsen Pahlevanzadeh
    Sep 9, 2013
  5. MRAB
    Replies:
    0
    Views:
    133
Loading...

Share This Page