[algogeeks] Re: Recursion in blobs

[Dhyanesh]

Your answer is absolutely right. It is indeed O(n). This algorithm is more commonly known as Depth-First Search (DFS). It is used for a variety of problems. Google for depth-first search and you will get more results.
-DhyaneshOn 1/26/06, H. [EMAIL PROTECTED] wrote:
Today in a data structures class we went over blob recursion. What wewent over is actually described on this page (different school though):
http://www.bowdoin.edu/~ltoma/teaching/cs107/fall05/Labs/lab9.htmlI understand how the recursion works, but I'm more interested indeterming the exact algorithm. I asked the professor, and he didn'tknow, except to say that it was very inefficient
I toyed around with it a for a few minutes tonight, trying to determinethe worse-case efficiency if all squares will filled in a playing fieldof x*y=n squares. I think I'm doing something wrong, because my initial
figur ended up with 9n, which would be Big Oh n, which I'm sure can'tbe right; it must be more inefficient than that.Any ideas? Both on how to go about determining the algorithm and theactual algorithm itself.

[algogeeks] Re: Recursion in blobs

[H.]

Wow, thanks! :-). It's very re-assuring to know that I got it right.

[algogeeks] Re: Recursion in blobs

[H.]

Thanks for the information. My google searches had been very
inefficient (I mean, blob algorithms juast hadn't gotten very far),
and now they will be that much more targeted.

[algogeeks] Re: Recursion in blobs

[Gene]

You can think of the grid as a (possibly disconnected) undirected
graphs where each filled grid square is a vertex connected by edges to
its neighboring filled squares.  Then the algorithm is a depth-first
search.  This is obviously O(n) where n is the number of _filled_
squares.