«

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.

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.

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[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

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

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[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)?

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

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

"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 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)

In article < .com>,
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?