logoalt Hacker News

mwkaufma • yesterday at 6:13 PM • 3 replies • view on HN

You've introduced an idiosyncratic definition of "worst-case" that nobody else uses to redefine proportional cycle-counting as "complexity", so yeah, I guess in your novel terminology that makes sense, but it isn't consistent with any CS textbook.

Replies

yorwba • yesterday at 7:38 PM

So I took literally the first complexity theory textbook PDF I could find https://theory.cs.princeton.edu/complexity/book.pdf#page=324 where we have

  Lemma 16.43
  Let ε > 0. For every n and k ≤ n there exists a (k, ε)-extractor Ext : {0, 1}^n × {0, 1}^t → {0, 1}^n
  where t = O(n − k + log 1/ε).
and of course the reason they do this is because later in Lemma 16.49, they have k = n − (s + 1) − log 1/ε, so that t = O(s + log 1/ε), canceling the n.

Admittedly, they never define Big-Oh notation for functions with multiple inputs or for non-integers like ε, but it's definitely standard notation, not something they or the Python developers idiosyncratically invented.

➕ show 1 reply
progval • yesterday at 7:44 PM

No, it's not just about cycle counting.

Worst-case O(n-k) complexity in general implies worst-case O(1) complexity for the set of cases where k=n-<constant>. There are still multiple cases, just a subset of those that don't include worst of the general case.

IsTom • yesterday at 7:39 PM

What are you talking about? There's a lot of expressions like O(n + k), O(n * k) or O(n * log k) in typical algorithm books (CLRS certainly has them). There's nothing special about O(n - k).