3 ms·
It'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
by Veedrac 11y ago
It'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.