An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.
An immutable data structure representing an array is definitely much slower than a mutable array (a contiguous piece of memory).
Usually != always, unfortunately :(
> An immutable tree is often about as fast as a mutable tree, it's just pointer manipulation in either case.
This might be true, depending on what type of processing you're doing, and if you have a good garbage collector.
Of course, if you're allowed to use mutable trees, then you should just use a hash table which will be faster both asymptotically and in practice.
I don't think this is true. Clojure uses immutable persistent data structure under the hood, just as most functional languages do, and devs often jump through hoops to circumvent them for performance reasons, opting instead for bit bashing like most other languages.