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. 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.
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
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)?
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
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 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 loadtime
rather than runtime. 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" <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
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.
BigOh 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 bigOh notation.

Pete Becker
Dinkumware, Ltd. ( http://www.dinkumware.com)
In article <11**********************@o13g2000cwo.googlegroups .com>,
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?
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.
"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.
BigOh 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 bigOh 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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...

by: truckaxle 
last post by:
I am trying to pass a slice from a larger 2dimensional 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...

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,...

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

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

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

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

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

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

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

by: veera ravala 
last post by:
ServiceNow is a powerful cloudbased platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...

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

by: jianzs 
last post by:
Introduction
Cloudnative applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...

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

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

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

by: stefan129 
last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multidomain SSL certificates? Any recommendations on reliable providers or specific...

by: egorbl4 
last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это
Что это? Что мне с этим делать?
...
 