mikolalysenko / dynamic-forest

Maintain a dynamic spanning forest of a graph under edge insertions and deletions
MIT License
84 stars 6 forks source link

Usage of "splice" results in linear running time #3

Open btrekkie opened 5 years ago

btrekkie commented 5 years ago

The edge list mutator methods insertEdge and removeEdge call Array.splice. It looks like the splice method takes Θ(n) time in popular JavaScript engines. (I'd be happy to be proven wrong, however.) As a result, the running times of link and cut() are at least linear in the total number of vertices. However, README.md states that updates take O(log2V) time, which is presumably the intention. It is possible to achieve this running time (at least, amortized with high probability) by storing the edges in linked lists rather than arrays, thereby avoiding the calls to splice. (You could even use binary search trees in place of sorted arrays if desired.)