Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg

Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg n). In practice, there are also many cases which ends up on the stack and never reaches the heap, so the memory allocation needs are somewhat smaller than what people think. Another point is that short-lived garbage is collected in O(1) time in the GC. So you don't pay for its collection either. Things are slower than a mutation, but the overhead is lower than people tend to think.