3 ms·

When you say log n slowdown, what is n here? The length of the program? Or something completely different?

• dan-robertson 5y ago
  I think the theme is ‘you can’t do arrays; the best approximation is made of trees, hence log n in the size of the array vs 1’.
  • remexre 5y ago
    Though I think Clojure has a linear datastructure that's O(log32(n)) for all the common ops. (This is the one with all the memeing because someone called it "practically O(1)".)
    • dan-robertson 5y ago
      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
      • kaba0 5y ago
        Why do you have a constant before the log term? Isn’t that completely meaningless?
        • 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 ago
            malloc isn't typically O(n) though, so I don't think that's reasonable math?