[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)?