Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents, excepting a full copy which free due to it being unnecessary.
It's not really clear what you mean by "order of magnitude" here. The notation you're using suggests that you're thinking in terms of asymptotic algorithmic resource requirements, which are most often characterized by polynomial degree; an order of magnitude ("factor of 10") is invisible in those terms.
But a factor of log n, while not invisible, is nearly so. If you're thinking in terms of polynomial degree, a factor of log n is literally an infinitesimal value - it's more than 0, but less than all positive real numbers.
But this doesn't apply to hashset because hashmaps are sparse, and stored as pairs, meaning that they're effectively base 16. Also the clojure implementation of sets is just hashmaps where the key is the same as the value.
Technically true, but only because a change to a vector of under 32 elements is O(1) by definition (as long as the algorithm is deterministic) and O(n) includes O(1). It's equally true that a change to a vector of under 32 elements is O(n!).
The notation you're using is not meaningful in the context of bounded input. Big-O notation is not concerned with any behavior except the behavior at infinity.
Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
That isn't good usage, but there was enough context in your comment to guess that that was what you meant.
The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.)
So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be?
The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
(Note that if k is not an integer this isn't really a polynomial.)
Also, if you care about that then you can use transients (if no one knows you mutated the data structure then it still counts as immutable) or mutable structures - both of which are pretty simple.