# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sat, 18 May 2013 17:47:38 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 6 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: The complexity of My AlgorithmPosted: Sun, 17 Jan 2010 18:56:36 UTC
 Senior Member

Joined: Wed, 4 Feb 2009 19:43:49 UTC
Posts: 100
Hi all,
I have the following Algorithm which I simply want describe in words to make it simpler to understand. My goal is to double check if I am right about its complexity.

I have a grid of lines (n*n). Each line represents a linked list which stores a node and the content of that node is the length of the line. Say I want to cover these lines by circles randomly placed on them. In other words, I want to place randomly a circle which covers a line(s). Based on the intersection of this circle (knowing its position and the intersected lines positions with the circle) we go to each line and then modify the content of the node by reducing its value as if the line became shorter (covered). We stop once all the lines have been covered by the circles (i.e., all the nodes in the linked lists have value of zeros). Now if the word "randomly" confuse you we can just assume for now that after a period of time the grid will be fully covered (We talk later about this).

The way that I think that this algorithm should be implemented is in linear time since I am dealing with an array of linked lists and based on the known position of a node and the positions of the intersected lines, we can easily know which lines to modify their linked lists.
So I would say that this algorithm has a complexity of O(n). What do you think?

Top

 Post subject: Re: The complexity of My AlgorithmPosted: Mon, 1 Feb 2010 13:48:38 UTC

Joined: Mon, 1 Feb 2010 13:31:34 UTC
Posts: 5
Location: Athens, Greece
tarektarek wrote:
Hi all,
I have the following Algorithm which I simply want describe in words to make it simpler to understand. My goal is to double check if I am right about its complexity.

I have a grid of lines (n*n). Each line represents a linked list which stores a node and the content of that node is the length of the line. Say I want to cover these lines by circles randomly placed on them. In other words, I want to place randomly a circle which covers a line(s). Based on the intersection of this circle (knowing its position and the intersected lines positions with the circle) we go to each line and then modify the content of the node by reducing its value as if the line became shorter (covered). We stop once all the lines have been covered by the circles (i.e., all the nodes in the linked lists have value of zeros). Now if the word "randomly" confuse you we can just assume for now that after a period of time the grid will be fully covered (We talk later about this).

The way that I think that this algorithm should be implemented is in linear time since I am dealing with an array of linked lists and based on the known position of a node and the positions of the intersected lines, we can easily know which lines to modify their linked lists.
So I would say that this algorithm has a complexity of O(n). What do you think?

Your question and algorithm description are rather unclear to me.

How many lines are there? Is there one linked list in each line or N linked lists in each line? How many linked lists do you have in total? How many nodes does each linked list have? What do you mean by "circle"? A circle is a set of points, but you're not talking about points here you're talking about nodes, so please define your context.

Thanks!

Top

 Post subject: Posted: Wed, 17 Feb 2010 20:29:34 UTC
 Senior Member

Joined: Wed, 4 Feb 2009 19:43:49 UTC
Posts: 100
Thank you dionyziz for the follow-up.

>>>How many lines are there?
It depends on the distances between any pair of lines, so say that for 9*9 (n*n), with spacing between any pair of lines is equal to 3m (N). We have the following

|------------|-------------|
|!!!!!!!!!!!!|!!!!!!!!!!!!!|
|------------|-------------|
|!!!!!!!!!!!!|!!!!!!!!!!!!!|
|------------|-------------|

(3 horizantal lines and 3 vertical lines)

By the way n and N can be arbitrary. BTW "!" only means a space where as | and - form lines.

>>>Is there one linked list in each line or N linked lists in each line?
For Each line, there is one linked list.

>>>How many linked lists do you have in total?
In the above example it is 9 linked lists.

>>>How many nodes does each linked list have? What do you mean by "circle"? A circle is a set of points, but you're not talking about points here you're talking about nodes, so please define your context.
Each time I randomily place a circle (i.e., sensor node such that it has a sensing circle) one at a time until all these lines are fully covered by some sensing circles.
so each time I do this, I might end up with different set of sensor nodes on the gird. Regarding the sensing circle, I am checking if the circle intersects one or more of the lines. when I am talking about a node (without mentioning the word sensor next to it), I mean a node in the linked list.

One more thing the sensing circle as a raduis R and also it is arbitrary.

Thank you.

Last edited by tarektarek on Mon, 10 May 2010 14:55:50 UTC, edited 1 time in total.

Top

 Post subject: Possibly O(N) or O(n^2)Posted: Tue, 2 Mar 2010 02:30:47 UTC
 Senior Member

Joined: Sun, 31 Jan 2010 05:07:26 UTC
Posts: 88
I'd think it'd be important to know for certain what role the circle (sensor) plays in your analysis. The algorithm can be much more efficient and simple if you can use little sensor radii towards the end.

However, if you're trying to do something with the sensors, like finding the minimum number of sensors required, it could get more complicated.

The algorithm seems like it will run in , where is the number of entries that you must check inside each sensor radius. If you don't need to worry about the circles at all, it can run in :D

Otherwise, you may want to consider getting a little more complicated...

I hope that this helps

Top

 Post subject: Posted: Tue, 2 Mar 2010 03:47:32 UTC
 Senior Member

Joined: Wed, 4 Feb 2009 19:43:49 UTC
Posts: 100
Thank you Generator for the follow-up.
When you said that it can be O(n) or O(c*n), do you refer n to the number of sensor nodes? and for c do you refer it to the number of lines intersecting the sensing circle?

Since like I mentioned before n*n but from what you posted, I understood it as number of sensor nodes. Just want to make sure about something, that each line might have one more sensor covering it, say 2, to explain it more, suppose that the first sensing circle hit the line at a position where there are still some remaining uncovered parts of this line, so the second sensor node came and covers these parts.

Last edited by tarektarek on Mon, 10 May 2010 14:55:30 UTC, edited 1 time in total.

Top

 Post subject: ClarificationsPosted: Tue, 2 Mar 2010 04:51:56 UTC
 Senior Member

Joined: Sun, 31 Jan 2010 05:07:26 UTC
Posts: 88
This seems like a fairly complicated problem...
We could temporarily define the following variables:

refers to the number of lines across the grid
refers to the TOTAL amount of positions in the grid
refers to the amount of circles or sensors in the grid
refers to the radius of a sensor

So going through the grid and covering all positions requires or covering checks, at the mininum. In the worst case, this could mean compares for each "covering check".

However, going through the grid also requires sensor placements which each require checks where refers to the geometric average of all sensor radii. This gives us approximately .

So far, we're still left with two running times and an initial estimate of:

I believe that we still should know more about the algorithm. Is this definitely the algorithm that you want to stick with? I ask this because we should know exactly how the sensor placement works to get a very exact estimate of the running time. The sensor placement could really change this.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 6 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous