3 ms·

The hypothesis of the statement doesn't hold. O(n log n) isn't greater than O(n log n).

• DanWaterworth 10y ago
  You have to evaluate it in a model with an explicit cache width size, then O(log_b(n)) < O(log(n))
  • GauntletWizard 10y ago
    log_b(n) * log(b) = log(n). log(b) is a constant in our algorithmic analysis, and can therefore be removed. There will never be a log_b(x^2) that grows at slower than log(x), no matter how big b is.
    • DanWaterworth 10y ago
      Which is why you have to evaluate in a model with an explicit cache width. In such a model, b is not a constant. The cache-oblivious model [1] is a fairly well-known example, but that won't work in this case, since we need to know b to set the tree width. Any of the other external memory models will do. [1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
      • ChuckMcM 10y ago
        I think the notation is imprecise. The quantity the author describes is commonly called the working set. His explicit thesis is that the time to process the working set is related to the size of the working set regardless of computational complexity. He spends the entire first part of his discussion belaboring this point with a linked list example. He goes on to do a systems analysis of the results and concludes that time of execution is system dependent not complexity dependent. Again using the same algorithm engaging with a larger and larger memory system. Generally engineers would experience this important principal in a more binary way, once their program started swapping to disk, its performance would fall through the floor. If you hold the size of the datum constant (and that is important), then processing fewer of them will take less time than processing more of them. The argument you make, as I understand it is as follows; Consider two algorithms that process N and P datums respectively to achieve the same computational result, and where N > P. There exists an algorithm such that P datums takes less per unit time to process than N. Resulting in a violation of my Lemma because Oi(P) > Oi(N) but Ot(P) < Ot(N). And you cite cache obliviousness as the principle that enables that violation. Would you agree that I have accurately summed up your argument?
        • DanWaterworth 10y ago
          It's roughly right, but it's not cache obliviousness that enables the violation. For the argument to work out, you have to evaluate it within a model that has an explicit cache and hence, treats big O results as being parametrized over the cache width.
  • SamReidHughes 10y ago
    O(log_b(n)) is the same as O(log n). With O(sqrt i) memory accesses you still have a constant factor separation between the absolute time performance of the two.
    • DanWaterworth 10y ago
      > O(log_b(n)) is the same as O(log n) Not in every abstract model. See other reply.
      • SamReidHughes 10y ago
        It has nothing to do with the model and is just a question of whether b is a variable in the big O notation. And in this case of O(sqrt i) memory access times, a binary tree and b-tree stay within a constant factor even as you vary b. (The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local.")
        • DanWaterworth 10y ago
          > It has nothing to do with the model and is just a question of whether b is a variable in the big O notation. There are models, like the cache oblivious model, where b is assumed to be a variable, so the model matters. > a binary tree and b-tree stay within a constant factor even as you vary b. it's not a constant factor if b is a variable. It's a factor of log b.
          • SamReidHughes 10y ago
            > it's not a constant factor if b is a variable. It's a factor of log b. It's between 1/(sqrt(2)-1) and sqrt(2)/(sqrt(2)-1), depending on how full the b-tree nodes are.
            • DanWaterworth 10y ago
              I don't know where you got those numbers from.