[remram]

From your link (emphasis mine):

> In each case, c is a positive constant and *n increases without bound*

It is indeed crystal clear what "asymptotic" means. If you have a definition for O-notation in non-asymptotic contexts, I have never heard of it.

[burntsushi]

I no longer understand where your confusion is, so I'm not sure how to respond. I'd suggest taking it back to what was actually said in the OP and the criticism it got. Otherwise, if you're arriving in ridiculous places like "you must be trying to say that O-notation is used in non-asymptotic contexts," then there's very clearly some kind of miscommunication or misunderstanding. From my perspective, your comments are terse, unclear and not addressing the central point directly.

[okl]

I try to explain with a practical example: Let's say I define a list with worst-case lookup time of O(n). Simplified this means that when I have a list of 100 elements and append 1 element, then the worst case lookup time increases from 100C to 101C where C is some constant time. The O(n) tells me how the runtime of the operation changes if I alter the input size.

Now the OP's idea is this: I'll fix the size of allowed elements in my list to some maximum value, lets say n=5, and then you always end up with the same worst-case time, O(1), because the input size is constant. With 5 elements it looks silly but you could say n = (very large number that won't be exceeded ever) and conclude that O(n=1). In OPs case the n is the number of bits in the key (implies a radix-tree)

=> If an algorithm is defined as being unscalable (fixed input), what sense does it make to describe that it scales constantly with input size?

[burntsushi]

I agree with everything you said, but I don't see how it leads the OP's formulation being silly or wrong or not useful. Here's another example (of my own) where you can pick an upper bound for `n` and base your complexity analysis around it. In this case, we're trying to provide an API guarantee that a search takes O(m+n) time despite wanting to use an O(mn) algorithm in some subset of cases. We can still meet the O(m+n) bound by reasoning that the O(mn) algorithm is only used in a finite set of cases, and thus collapses to O(1) time. Therefore, the O(m+n) time bound is preserved. And this isn't a trick either. That really is the scaling behavior of the implementation. See: https://github.com/BurntSushi/memchr/blob/ce7b8e606410f6c81a...

> If an algorithm is defined as being unscalable (fixed input), what sense does it make to describe that it scales constantly with input size?

I'll answer your question with another: in what cases does it make sense to describe the scaling behavior of an algorithm as O(1)?

[remram]

Everybody else in this thread is getting it, while you are only leveling personal attacks at me with no arguments whatsoever. Terse, ridiculous, confused, errant niggling? Why is this the way you have to communicate?

[burntsushi]

I'm sorry for coming across harsh. I tried to stick to commentary about your words, not you as a person. That's why I said "your comments are." I legitimately find your commenting here rather frustrating. It feels to me like you're posting zingers instead of trying to come to a mutual understanding.

I'll try one last time. I personally feel like this answer[1] very clearly refutes the criticism leveled in the top-level comment[2]. Specifically, the opening parts of the answer:

> It depends on the computational model you choose. It is obviously not true that two numbers can be added together in constant time regardless of their size. If you think about it in terms of the most elementary operations, those on individual bits, adding two n-bit numbers would require O(n) elementary operations. And multiplying two n-bit numbers would use O(n2) elementary operations if you do it using long multiplication. You can easily try this out for yourself using pen and paper.

> The problem with this viewpoint is that it makes analyzing algorithms very tedious. Any time we would add two numbers a and b we would have to figure out that they would have loga and logb bits respectively and that the addition would take O(loga+logb) time. This would make the analysis much more tedious, and result in running time with lots of logs in them.

And thus, by convention, big-O notation typically uses an `n` that is defined in terms of units of bits and not just bits themselves. This is why it can make sense to declare something O(1) even when it might actually be O(logn) where n is the number of bits in the input.

[1]: https://cs.stackexchange.com/a/140646

[2]: https://news.ycombinator.com/item?id=38511259

[remram]

> And thus, by convention, big-O notation typically uses an `n` that is defined in terms of units of bits and not just bits themselves. This is why it can make sense to declare something O(1) even when it might actually be O(logn) where n is the number of bits in the input.

I don't disagree with this at all, now the question is: what is n in the case we are talking about? That goes to infinity as we evaluate the cost of this cache system, allowing us to use *asymptotic O notation*?