Math definition goes something like this: f(n)=O(g(n)), if exists C such that f(n) < C x g(n), when n goes to infinity.

Function “quickSortExecutionTime(permutation)” depends on exact input (each permutation/shuffle has different exec time), parameter “permutation” can not go to infinity, so it can’t be used with O(n) directly. (Parameter need to be single real number)

QuickSortWorstCaseTime(n) is single valued function thus, it can be used with O(n) notation. Same is true for quickSortAvgCaseTime(n) and quickSortBestCaseTime(n).

But you answered my question. (Very indirect “Yes” :) )

Not according to my understanding of the subject, my copy of "Introduction to Algorithms", and Wikipedia.

Big O is an upper bound for a function growth - being O(f(n)) means growing asymptotically slower than f(n) (up to a multiplication by a constant).

Small o is a lower bound for a function growth - being o(f(n)) means growing asymptotically faster than f(n) (up to a multiplication by a constant).

Big theta means the function grows exactly that fast - being Θ(f(n)) means the function is both O(f(n)) and o(f(n)), so being exactly f(n) up to a multiplication by a constant. In practice, due to typographical limitations, people use O(n) where Θ(n) would be more precise.

Average case, best case, worst case, amortized etc complexities are a wholly different thing. For example, quick sort is Θ(n^2) worst case and Θ(n log n) average case.

I'd love to read it if it did, but honestly I wonder if enough's changed to warrant a new edition. Everything I'm reading now is still relevant.

I poked through a few messages in that thread and while there is a space benchmark, there is no time benchmark, something I would expect to see on switching from a LL to a cache-aware implementation. Phoronix, who would benchmark a potato if you told them it gave you better performance, has an article with no benchmarks. The commit says it should be good enough for someone to run a perf benchmark.

Is it common to add an unused data structure into the kernel without understanding its performance characteristics? If they are available it is not obvious to someone who has read the article, read the commit message, read lkml, went looking for benchmarks, and has still come up with no concept of how this might perform in realistic or synthetic scenarios.

I'm pretty sure pphysch is correct.

> Seriously, a simple google search or taking a minute to follow the first link in the article would have shown you that the patch set obviously came with a benchmark [1].

If you're referring to the table with headers "number xarray maple rhash rosebush", it's an estimate of memory usage, not a benchmark. And the author (Matthew Wilcox) says "I've assumed an average chain length of 10 for rhashtable in the above memory calculations", which folks questioned. So there's reason to doubt its correctness.

> It’s someone posting a patch to the kernel mailing list, not some random kid on GitHub, there is no point assuming they are an idiot to try to shine.

Let's just let the work speak rather than flagging the author as an idiot or genius...at present rosebush is unproven and based on questionable assumptions. That might change in future rounds.

The entire point of a LWN article like this is to accurately summarize the patch sets and email discussions for casual readers. No need for the snark.

That would be fine, except that in v2 the buckets are fixed size.

What happens when more than 20 objects end up with the exact same hash?