2 ms·
Are there (non-contrived) algorithms where adding extra pointer indirection increases the complexity? I would say you could transform O(2n) into O(4n), and in p
by dtech 11y ago
Are there (non-contrived) algorithms where adding extra pointer indirection increases the complexity? I would say you could transform O(2n) into O(4n), and in practice this matters, but not O(2n) into O(2n^2).
- Veedrac 11y agoIt's the other way around - removing pointer indirection would ruin their complexities. If a tree is an unshared value type (eg. there are no references), then a functional tree update is O(n). Using shared references, this is O(n²). Cyclic data structures without pointers are of unbounded size. De-structuring a type (X, Y) is O(sizeof(X) + sizeof(Y)) without pointers, but O(1) with. Tons of examples.
- Veedrac 11y ago> If a tree is an unshared value type (eg. there are no references), then a functional tree update is O(n). Using shared references, this is O(n²). I meant O(n) vs O(log n) of course. Not sure what happened there.