473,221 Members | 2,001 Online

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

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.

Nov 22 '05 #1
12 7939
pj*****@gmail.com 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.
Nov 22 '05 #2

red floyd wrote:
pj*****@gmail.com 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

Nov 22 '05 #3
rwf_20 wrote:
red floyd wrote:
pj*****@gmail.com 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)?
Nov 22 '05 #4
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

Nov 22 '05 #5
In article <_7*******************@newssvr11.news.prodigy.com> ,
red floyd <no*****@here.dude> 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
em****@soda.CSUA.Berkeley.EDU
Nov 22 '05 #6
pj*****@gmail.com 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

Nov 22 '05 #7

"E. Mark Ping" <em****@soda.csua.berkeley.edu> wrote in message
news:dl***********@agate.berkeley.edu...
In article <_7*******************@newssvr11.news.prodigy.com> ,
red floyd <no*****@here.dude> 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

Nov 22 '05 #8
Howard wrote:
"E. Mark Ping" <em****@soda.csua.berkeley.edu> wrote in message
news:dl***********@agate.berkeley.edu...
In article <_7*******************@newssvr11.news.prodigy.com> ,
red floyd <no*****@here.dude> 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)
Nov 22 '05 #9
mlimber <ml*****@gmail.com> 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?
Nov 22 '05 #10
Even for very large arrays, the method you provide should only add a

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.

Nov 22 '05 #11

"Pete Becker" <pe********@acm.org> wrote in message
news:4q********************@rcn.net...
Howard wrote:
"E. Mark Ping" <em****@soda.csua.berkeley.edu> wrote in message
news:dl***********@agate.berkeley.edu...
In article <_7*******************@newssvr11.news.prodigy.com> ,
red floyd <no*****@here.dude> 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

Nov 22 '05 #12

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.

--

Nov 22 '05 #13

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 22 by: VK | last post by: A while ago I proposed to update info in the group FAQ section, but I dropped the discussion using the approach "No matter what color the cat is as long as it still hounts the mice". Over the last... 11 by: truckaxle | last post by: I am trying to pass a slice from a larger 2-dimensional array to a function that will work on a smaller region of the array space. The code below is a distillation of what I am trying to... 6 by: Brian Henry | last post by: I was wondering how you guys would handle filling a list view with something like 10,000 items which each have 10 sub items on them... there has to be major speed issues with that right? Yet,... 2 by: laredotornado | last post by: Hello, I am trying to parse a CSV file. I am counting on the fact that there will be 10 entries per row while (($data = fgetcsv($handle, 1000, ",")) != FALSE) { but that is not always... 3 by: John Espinosa | last post by: I am new to C#. I am trying to use a for loop of integers to fill up a String array. Actually, I am trying to get a dropdown list of all the days in the current month. This is what I have been... 49 by: vfunc | last post by: If I have a large array 10,000+ elements then how do I reserve memory for this ? Currently I get a segmentation fault. Dynamic reservation is good, but allowing a chunk for the program is an... 272 by: Peter Olcott | last post by: http://groups.google.com/group/comp.lang.c++/msg/a9092f0f6c9bf13a I think that the operator() member function does not work correctly, does anyone else know how to make a template for making two... 26 by: aruna.mysore | last post by: Hi all, I have a specific problem passing a function pointer array as a parameter to a function. I am trying to use a function which takes a function pointer array as an argument. I am too sure... 6 by: lukasso | last post by: Hi, this is my code that should produce something like a timetable for a few days with each day divided into 30 minute pieces. It makes query from MySQL and then creates a 2d \$array which then is to... 1 by: isladogs | last post by: The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike... 0 by: veera ravala | last post by: ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow... 3 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In... 0 by: jianzs | last post by: Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from... 0 by: abbasky | last post by: ### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method... 2 by: jimatqsi | last post by: The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art... 0 by: fareedcanada | last post by: Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like... 0 by: stefan129 | last post by: Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific... 0 by: egorbl4 | last post by: Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...