Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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.

 
Reply With Quote
 
 
 
 
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.
 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
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)?
 
Reply With Quote
 
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)
 
Reply With Quote
 
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

 
Reply With Quote
 
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





 
Reply With Quote
 
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)
 
Reply With Quote
 
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?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Graeter than or less than bbawa1@yahoo.com ASP .Net 4 06-21-2007 08:03 PM
Shell not filling less than 5KG cylinders RayC NZ Computing 12 06-21-2006 09:32 AM
Tastes great, less filling Don Hills NZ Computing 4 05-15-2006 07:39 AM
regex problem: 'greater than' 'less than' and 'equals' not matching! falcon Java 10 02-24-2006 01:23 PM
Time on Update is exactly 3 hours less than time entered Ray Wood ASP .Net Web Services 0 07-17-2003 02:06 PM



Advertisments