3 ms·

What? Saying something takes O(1) time or space is absolutely meaningful. https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions https://en.wi

What? Saying something takes O(1) time or space is absolutely meaningful. https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...

okl 3y ago
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 3y ago
  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 3y ago
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 3y ago
  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 3y ago
    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 3y ago
      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 3y ago
        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 3y ago
        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/ce7b8e606410f6c81a63f45abb24c5b5aab5d741/src/arch/all/rabinkarp.rs#L24-L31 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)?

okl 3y ago

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 3y ago
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 3y ago

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 3y ago
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 3y ago
  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 3y ago
    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 3y ago
      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 3y ago
        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/ce7b8e606410f6c81a63f45abb24c5b5aab5d741/src/arch/all/rabinkarp.rs#L24-L31 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)?