3 ms·

If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. T

If I ask for something to be done in O(1) I'm not asking for it to be fast, I'm asking for it to take the exact same amount of time every time no matter what. That might end up being slower, but so what, maybe that's what I need. If I ask for an O(1) algorithm and you build something that is as fast as possible, faster in every case, but sometimes it's really fast and sometimes it's a little less fast but still fast -- well, then it's not O(1) and not what I asked for. It may be fast, but if it's sometimes faster than at other times it's not O(1). Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest.

indeed30 5y ago
I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.
- lmilcin 5y ago
  Well, not exactly. What it really means is that the execution time does not depend on the size of input (n). What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time. For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.
  - peferron 5y ago
    > an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute. According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) <= M * 1. But according to your own words there's no upper limit to 1/(randFloat()), therefore there's no such constant M, therefore it's not O(1). (In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)
    - randomswede 5y ago
      More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class. What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.
      - dcow 5y ago
        https://www.quora.com/Why-isnt-infinity-a-constant https://www.quora.com/Why-isnt-infinity-a-constant
deleted 5y ago
[deleted]
sagarm 5y ago
A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1). Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.
CRConrad 5y ago
> Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest. Maybe not synonymous in the sense of technically exactly equal, but certainly a pretty good approximation -- and absolutely synonymous in the sense that the whole purpose of big-O notation is to be able to reason about speed in more general terms, comparing algorithms in pseudo code in stead of having to actually write the program so you can run it through a benchmark. So, no: If "the best possible big-O, O(1), does not necessarily mean the fastest," then it isn't actually the best.

indeed30 5y ago

I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.

lmilcin 5y ago
Well, not exactly. What it really means is that the execution time does not depend on the size of input (n). What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time. For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute.
- peferron 5y ago
  > an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any possible floating point number with equal distribution, is still O(1) algorithm, even though there is no upper limit on how long it can take to execute. According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) <= M * 1. But according to your own words there's no upper limit to 1/(randFloat()), therefore there's no such constant M, therefore it's not O(1). (In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)
  - randomswede 5y ago
    More a case of "f(n) = 1/randFloat() does not have a well-defined limit as n goes to infinity", so it would be hard to say that it fits in ANY complexity class. What is, however, clear is that its run-time does not depend on the size of the input. And technically, that means we can find a constant (infinity) that always... But, that is pretty unsatisfying.
    - dcow 5y ago
      https://www.quora.com/Why-isnt-infinity-a-constant https://www.quora.com/Why-isnt-infinity-a-constant

deleted 5y ago

[deleted]

sagarm 5y ago

A hash table has E[O(1)] inserts and lookups. Most people ignore the expected part and just say those operations are O(1). Asymptotic complexity is of course only loosely correlated with speed. In real systems with real workload sizes, constant factors matter a lot.

CRConrad 5y ago

> Thus, I do not consider big-O to be synonymous with speed. They are different, because the best possible big-O, O(1), does not necessarily mean the fastest. Maybe not synonymous in the sense of technically exactly equal, but certainly a pretty good approximation -- and absolutely synonymous in the sense that the whole purpose of big-O notation is to be able to reason about speed in more general terms, comparing algorithms in pseudo code in stead of having to actually write the program so you can run it through a benchmark. So, no: If "the best possible big-O, O(1), does not necessarily mean the fastest," then it isn't actually the best.