[TheLoneWolfling]

Why O(n log n) space? Because you require O(n) connected components in the worst case, which means that you need O(log n) space per cell in the worst case. Although now that I think about it that pushes the amount of time to O(log n).

In practice you can treat it as O(1) time and O(n) space, though.

Also, that preprocessing with result saving is substantially slower than the connectivity alone. The connectivity alone is O(n) / O(n log n) preprocessing time - you check each cell a maximum of 5 / 9 times (depending on 4 or 8 way connectivity).

Also, that preprocessing with result saving fails miserably when you do updates to the graph.

[ajuc]

But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

So it is O(N) in space?

I'm not sure we're talking about the same thing. I mean space requirements for the results of preprocessing.

Preprocessign itself may require computing cluster for all I care.

[TheLoneWolfling]

> I'm not sure we're talking about the same thing.

We are.

> But you can just write for each cell the index of component it belongs to. It can't belong to many, right?

Right. Each cell belongs to 1 and only 1 connected component.

However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance.

As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall.

In practice you can treat this as effectively O(n), however.

[ajuc]

So you treat 1 integer as log n? That's very technical, but in that case OK.

[TheLoneWolfling]

Yes. Although, as I said, in practice you can treat the integer index as constant space.