Hacker News Reader

Comment by mwkaufma | Hacker News Reader

Isn't O(n - k) or O(len(l1) + len(l2)) just O(n)? Instead of blurring the line between complexity-analysis and cycle-counting, just print both the complexity and the est proportional cycle-count as separate measures.

View on HN

I think it's not unreasonable or uncommon for big O to track separate variables without reducing them, just to highlight the (lack of) sensitivity of different parameters.

If k = n - constant it comes out to O(1).

Every O(n) is O(1) if n = 1. Complexity measures worst-case by-definition, not all cases.

It has two parameters and depending on their relation it will act differently, it's reasonable to include this information. It is worst case O(1) when n and k don't differ much.

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.

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.

So long as f,g: N→M 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_n∈N ‖f(n)‖/‖g(n)‖ < ∞.

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

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.

Saying that l.pop(k) has time complexity O(n-k) implies that popping something at position 5 from the end has bounded (amortized) time cost regardless of the length of the list l, ie even if we let the list grow arbitrarily.

It's a stronger claim than just saying O(n), because in the latter case you wouldn't be able to conclude that popping something 5 from the end has bounded time as the list grows.

Complexity measures the worst-case, not the amortized case. If you want to report proportional cycles for more fine-grained per-feedback, fine, report proportional-cycles, but that's not Big-O, so don't use that notation.

Worst case can mean two things. For fixed n, worst list content and worst k, which gives you the less fine-grained O(n). For fixed n and fixed k, worst list content, which gives you the fine-grained O(n - k).

Edit: Another example of that is the complexity of convolutional filtering, which is O(n min(log n, k)) for a signal of length n and a kernel of size k.

Big O notation has nothing to do with worst or best case. f = O(g) simply means that f is asymptotically bounded by a multiple of g.

Well, yes, but if k is for example Ω(n) then O(n-k) is also O(1).

Reply on news.ycombinator.com