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).

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.

> 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.

Well, maybe implementation detail is not a good way to put it. But as my other comment shows, I think he's even more worried about the semantics of the construct than how the machine executes it.

Sure; but he blames the type for its semantics. New languages have shown that

* even with the downsides, pointers are absolutely worth it, and

* the type's semantics can be improved, removing many of the types's problems.

I've never seen the big O infinity notation before, nice one, thanks.