So you treat 1 integer as log n? That's very technical, but in that case OK.
Re:PathFinding.js
by TheLoneWolfling on Thursday May 28, 2015 @07:42PM
(#9621886)
Yes. Although, as I said, in practice you can treat the integer index as constant space.
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.