Hacker News Reader

A complexity measure is a measure of complexity over a model. Mostly we talk about input size models, but we can (and do) talk about other models. It isn't a question of complexity scaling vs. time scaling, but of complexity scaling over an input size model vs. a machine architecture model.

There are tons of well-researched machine architectural models for complexity analysis. In the case of the article, any one of the many external memory (EM) or hierarchical memory models would be appropriate. These can capture latencies and bandwidth of hierarchical memories and storage, and in some cases even eviction, contention, partition, etc.

This isn't some esoteric point. In high performance computing, distributed algorithms, or even systems & architecture it's pretty much expected that if you talk about complexity, you should do so under some sort of EM model.

Well stated. That's a much better way to say it.

Don't think your conclusion holds - and that's actually something the author brings up.

It might be quicker in time (not in the amount of instructions executed) to calculate something multiple times, or to do a more complex calculation or what have you, in order to touch less memory.

> if Oi(f(N)) > Oi(g(N)), Ot(f(N) will be > Ot(g(N)).

That doesn't hold. Some instructions take longer than others.

If all instructions complete within some constant deadline independent of N/the input then it does hold even if they take different amounts of time.

It doesn't hold for binary tree lookups vs B-tree lookups.

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

You have to evaluate it in a model with an explicit cache width size, then O(log_b(n)) < O(log(n))

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.

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

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?

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.

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.

> O(log_b(n)) is the same as O(log n)

Not in every abstract model. See other reply.

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.")

> 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.

> 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.

I don't know where you got those numbers from.

> The reason is, the binary tree accesses that a single b-sized access replaces get exponentially more "local."

sqrt(n)+sqrt(n/b)+sqrt(n/b^2)+... versus sqrt(n)+sqrt(n/2)+sqrt(n/4)+...

And since b-tree nodes can be half empty, there's a sqrt(2) uncertainty. (And of course there is no other memory overhead at all, none whatsoever.)

Thanks, I see. Are you assuming ephemeral usage of nodes to make that claim?

I don't know what that means. I'm assuming a random element of the tree is picked, that parent nodes are in a smaller or equal cache level than children, that all but one cache levels are used completely, that each cache level has O(sqrt n) access time, and that there is an upper bound on the ratio between successive cache sizes.

Or less generally: it takes sqrt(j) nanoseconds to dereference the pointer with value j, and parent nodes are at smaller addresses than their children.

Right, you're assuming there's one tree being maintained.

Or any fixed number of them, or any curve where the number is polynomially smaller than the total size...

The article demonstrates that memory access is an instruction that actually has O(n^1/2) performance.

This is how I would go about stating the proof.

1) The article shows that the time to process N datums of data is related to the size of the total data processed. And that as the size of the data set grows, the time to process it grows with the root of N.

2) Computational complexity's order of magnitude is relative number of datums need to be processed in order to complete the computation.

3) Less complex computations process fewer datums, fewer datums mean a smaller total memory footprint.

Therefore, processing fewer datums will lower your total memory processing cost which will lower your total time. Q.E.D.

Q.E.Nope. Memory can get reused.

Does that really follow? The sqrt(N) factor is the overhead of memory access only, so if you're comparing an algorithm where every operation is a memory access to another where that is not the case it would seem you could have the inverse relation in Oi and Ot.

Edit: A counterexample then:

Oi(f(N)) = N^(2/3) (memory accessing operations) Oi(g(N)) = N (non memory accessing operations)

Ot(f(N)) = N^(7/6) Ot(g(N)) = N

So Oi(f(N)) < Oi(g(N)) but Ot(f(N)) > Ot(g(N))

I just assume that every big-O equation has some sort of units (possibly implicit) and that neither the inputs nor the results are dimensionless quantities.

We just tend to assume that "N" is clear from context and that the result is some number of similarly-loose "instructions".

Your Lemma doesn't hold if the time to execute one instruction is dependent on N - which is pretty much the entire point the blog post makes.