Right, and updates are also O(32 log32(n)) rather than O(2log2(n)), rather than O(1) for arrays. It’s a bit more complicated when you think about cache lines being updated but mutable arrays massively win on cache

Why do you have a constant before the log term? Isn’t that completely meaningless?

It is meaningless mathematically. It’s as meaningless as the parent talking about log32(n) because of course log32(n) = log n / log 32, so there is just a constant of 1 / log 32 being put at the front.

I think the subtext is really a statement about constant factors. The parent is saying “if trees are wide then lookups are cheap” and I am saying “if trees are wide then updates may be expensive” (to update an immutable binary tree of size n, you must allocate log2(n) nodes of size (say) 3. To update a 32-ary tree you need log2(n) / log2(32) = log2(n) / 5 nodes of size 33 so, as 33/5 = 6.6 > 3, the wider tree requires more allocation for updates.)

malloc isn't typically O(n) though, so I don't think that's reasonable math?