Velocity Reviews > C++ > Filling 2d array in less than O(n^2) time

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

pjhyett@gmail.com
Guest
Posts: n/a

 11-18-2005
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[i][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.

red floyd
Guest
Posts: n/a

 11-18-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) 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[i][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.

rwf_20
Guest
Posts: n/a

 11-18-2005

red floyd wrote:
> (E-Mail Removed) 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[i][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

Markus Moll
Guest
Posts: n/a

 11-18-2005
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

red floyd
Guest
Posts: n/a

 11-18-2005
rwf_20 wrote:
> red floyd wrote:
>
>>(E-Mail Removed) 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[i][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)?

E. Mark Ping
Guest
Posts: n/a

 11-18-2005
In article <_7sff.15956$(E-Mail Removed)> , red floyd <(E-Mail Removed)> 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-Mail Removed) mlimber Guest Posts: n/a  11-18-2005 (E-Mail Removed) 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[i][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 Howard Guest Posts: n/a  11-18-2005 "E. Mark Ping" <(E-Mail Removed)> wrote in message news:dlljok$1isk$(E-Mail Removed)... > In article <_7sff.15956$(E-Mail Removed)> ,
> red floyd <(E-Mail Removed)> 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

Pete Becker
Guest
Posts: n/a

 11-19-2005
Howard wrote:

> "E. Mark Ping" <(E-Mail Removed)> wrote in message
> news:dlljok$1isk$(E-Mail Removed)...
>
>>In article <_7sff.15956\$(E-Mail Removed)> ,
>>red floyd <(E-Mail Removed)> 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)

Greg Comeau
Guest
Posts: n/a

 11-19-2005
In article <(E-Mail Removed) .com>,
mlimber <(E-Mail Removed)> 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?