[justAlittleCom]

I am sorry... but no, the article is interesting and well written, but it has nothing to do with big O notation. Random access in memory is still in O(1), it doesn't depend on the size of the data structure (I am assuming that is the "n" the author talk about by pretending that a memory access is O(sqrt(n)). Even if you have a very complex memory architecture with 15 caching levels, spread all over the world, if you have a maximum of 5 day delay for accessing your memory through the mail, it will still be O(1), because 5 day is constant, it does not depend on the size of the data structure.

The "n" the author is really talking about may be the depth of the cache hierarchy.

[xrstf]

Are your questions maybe answered in part IV of the series, the FAQ[1]?

[1] http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-pa...

[DanWaterworth]

There are models like the Transdichotomous model [1], where the properties of the machine vary based on the problem. That seems to be what is happening here.

[1] https://en.wikipedia.org/wiki/Transdichotomous_model

[ricardobeat]

What he tried to show is precisely that in practice it does depend on the size of the data structure.

[fisherjeff]

...but if you have a significantly smaller dataset, you don't need such a complex caching architecture, which brings faster access times at the margins. So even in your example, worst-case access time scales with dataset size.

[stdbrouw]

It's just a fun way to frame a conversation about cache/ram latency, relax.

[justAlittleCom]

I see the point and it is interesting, it's just not big O ^^ If I replace in my head all O(thing) by MyCustomComplexityMeasureYetToBeDefinedProperly(thing) then it makes perfect sens.

[exelius]

Big O is basically that. Big O notation predates computers (late 19th/early 20th century) -- it's simply a notation to signify how a problem scales in complexity in relation to the size of the data set. I would argue that multi-level memory access is itself a problem that scales complexity in the same way.

[arielb1]

You can say everything is O(1) because nothing would ever take more than `2^128` seconds. In practice, O-notation means "with a reasonably small constant".

[xenadu02]

> but it has nothing to do with big O notation

If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate.

Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now.

> Random access in memory is still in O(1)

No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage.

Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.

[krinchan]

Except Big-O was never intended to describe wall clock time. As soon as you try to use Big-O to describe a number of concrete units you'll fail. Big-O is purely a comparative measure, this algorithm vs. that algorithm. As it stands, it is fairly meaningless outside of purely academic exercises.

EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.

[Jweb_Guru]

Big-O isn't handwavey, it was absolutely intended to describe (among other things!) wall-clock time, and the article isn't just talking about constants. Also, many operations (like adding) are constant-time on modern computers, outside of memory hierarchy effects, ALU stalls, etc., since they're bound to finish within exactly one clock-cycle.

[lorenzhs]

Big-O is mathematically rigorously defined, but has nothing to do with wall-clock time. It's about the asymptotic behaviour of functions. How you interpret the values of these functions is up to you - of course you can model wall-clock time, but then you'd probably be interested in all the constant factors and lower-order terms that asymptotics hide from you, so Big-O analysis is the wrong tool.

[Jweb_Guru]

If wall-clock time is being affected by non-constant factors (as the article convincingly asserts), why on earth wouldn't you want to model those factors with big-O notation? Moreover, why do you think that people uninterested in wall-clock time wouldn't care about constant factors, but people interested in wall-clock time unilaterally would?

[lorenzhs]

If your program does two steps, one of which takes time O(n) and the other O(√n), then your program takes time O(n) because that dominates. That's an example of lower order terms. If you measure wall-clock time, then you'd be interested to know about that second step. But if you're looking at asymptotic analysis, then it's completely irrelevant because the linear term dominates it.

Your other questions are all best answered by: Big-O notation is not the right tool if you want to make predictions about wall-clock time. I don't think I need to justify why someone interested in wall-clock time would be very interested in the constant factors involved - the difference between n and 20n is a factor of twenty, and whether a program takes half a second or ten does make quite the difference.

But asymptotically, they're the same. Someone who is interested in the asymptotic behaviour wants to know how fast the function grows - is it linear? linearithmic? quadratic? cubic? exponential? (with which base - 1.1^n, 2^n, 10^n?). For them, a constant factor isn't interesting.

Of course, neither extreme is particularly helpful when trying to compare algorithms in practice. Modelling the hardware extensively and including all the little constant factors is exceedingly tedious, even if you can actually get all the information required to do so. Pure asymptotics also don't help much if they hide huge constant factors. That's why Algorithm Engineering is a thing (and a very good thing!). Basically, it tries to bridge the gap between algorithms that theorists like, and those that practitioners use. To that end, design, analysis, implementation, and experimentation must form a circle and influence each other. Wikipedia probably does a better job of explaining it, though.