logoalt Hacker News

yorwbayesterday at 7:38 PM1 replyview on HN

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.


Replies

jasomilltoday at 2:01 AM

So long as f,g: NM and we have a reasonable definition of the magnitude ‖·‖:M→ℝ, it shouldn't matter what N is, since we can just define

O(f(n)) = O(g(n))

if and only if

sup_nN ‖f(n)‖/‖g(n)‖ < ∞.