[remram]

Still it's a notation that had meaning, about the behavior as n goes to infinity. If you take out n, or if you don't have an n, just don't use it.

[burntsushi]

What? Saying something takes O(1) time or space is absolutely meaningful.

https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...

[okl]

Setting n=1 to say your O(n) is actually O(1) makes no sense because big O notation tells us how the time/space grow as function of the input size. If n=1, input size is fixed.

[burntsushi]

That's not what is happening here. The n cannot grow because the representation is fixed.

Read the links I've provided. The convention and meaning are clear here.

[remram]

O notation has meaning if something is 'n' and that 'n' can grow. Without an n defined somewhere, nothing can be O(n), nothing can be O(1).

[burntsushi]

I think the links I've provided sufficiently explain what the common convention is. And in the context in which the notation is used here, it is crystal clear what is meant.

This feels to me like errant niggling for the sake of it.

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

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