(The language implementation can of course engage in strategies to avoid a full array copy, that you as the user have little insight into, but these are often questionable as they slow down run time in other cases, and anyway, they can only mitigate this problem, which is not going to go away.)
Uh, most good implementations of languages with immutable arrays perform O(1) or O(log n) array updates. The two I use most, Mercury and Erlang, both do (O(1) and O(log n) respectively).
If you, the user, has "little insight" into the runtime of data structures you're using, you have bigger issues. Every standard library I've ever seen guarantees the asymptotic behavior of hash tables, sets, linked lists, etc. Immutable arrays are no different.
