3 ms·
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 const
by dan-robertson 5y ago
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.)
- remexre 5y agomalloc isn't typically O(n) though, so I don't think that's reasonable math?