2 ms·
That lookup can be done in constant time, rather than linear, right?
by jfkebwjsbx 7y ago
That lookup can be done in constant time, rather than linear, right?
- simias 7y agoI'm not very good at big-O. I meant that in order to build the path I would need to lookup the neighboring nodes to find the closest to the target, then just to that node and continue until the end. So it's linear with the average distance I guess.
- tpxl 7y agoYeah, linear with regards to the number of nodes - double the amount of nodes and you'll need to do double the look-ups; and constant with regards to the number of streams - no matter how many streams, always the same number of look-ups.