4 ms·

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the con

by roel_v 8y ago

Sure that's what it is formally, but that's not the applied meaning the article is about. Take an hypothetical search algorithm that is O(1) except when the container you're searching is of length 50, then it's O(n). That makes the algorithm O(n), right? (yes this is a stupid contrived example, and I know one can make any case when one can make up any reality etc. - but I think it's a valid style figure in this case, to contrast the theoretical definition with the application). Would you toss out that search algorithm and say 'well we have algorithms that search in better than O(n) so forget about this one'? No, you'd do 'if (container.size() == 50) { return container.bisect_find(key); } else { container.lalaland_find(key); } And that's exactly the difference between the theoretical concept and the application. (although I'll admit that I started out writing the comment trying really hard to avoid the word 'average' because it's so confusing and then it still slipped in)

deleted 8y ago
[deleted]
joshuamorton 8y ago
No, that algorithm is O(1). 50 is a constant. As n -> infinity, the algorithm runs in constant time. Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)). So I choose f(n) == 1, and C == 100. Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1, so it is O(1).
- roel_v 8y ago
  Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )
  - joshuamorton 8y ago
    Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is). (If you reject that and claim that just because I can construct an algorithm that is O(1) from yours doesn't mean that your algorithm is O(1), I'll point out what you presented isn't technically a function, since its not mathematically pure, so the concept of Big-O is ill-formed)
    - roel_v 8y ago
      Well but (I think) what you're talking about now is the complexity of the 'wrapper' function I posed, not the complexity of the hypothetical algorithm I started out with. Yes you can add an indirection that converts it back into O(1) but the original, but that wasn't the point. I think. But then again, maybe what your second paragraph is saying is exactly that? I'll admit that I lost track of things somewhere between writing my original comment, switching back and forth to my code between compiles and now being back here :) Also, I don't understand what you mean by 'mathematically pure', but that's on my end.
      - robconery 8y ago
        The Big O of an algorithm does not change based on data size. Even if your set had precisely 1 record in it - the code you write, if it loops over every item in the set (even if it's only one item) - is still O(n).
        roel_v 8y ago
        Yes I know that - was this reply meant for another comment?
      - joshuamorton 8y ago
        So there's two ways of looking at it, the more handwavy is "my construction that treats your algorithm as a black box does only ever strictly more work than your algorithm. If mine runs in a constant number of operations, yours must as well." And certainly your algorithm runs in amortized constant time (which is a weird phrase). The other way is to ask "what is a function"? Normally, a sorting function is expressed as sort(List[Comparable]) -> List[Comparable] your sorting function however has a different way of working. It has an additional input, the time. Now you might argue that you aren't taking the time as input, but you are...somehow. So in reality, your function has a signature sort(int, List[Comparable]) -> List[Comparable] There's this extra int input which is weird, so you don't have. Computational complexity tools like O-notation don't concern themselves with such things. O notation only cares about how the runtime changes as the size of the input changes. If the size of the int "time" is bounded (which it is, since the max is 86400), then one of the inputs is constant. It can be ignored. Purity in this context is the idea that the function only acts on its inputs, there are no external forces that modify how it works. Pure functions are mathematical objects, impure functions aren't really. So once you convert your construction to being pure, it becomes more clear why the function is ill-formed: you've got this extra constant size input (that runtime analysis can ignore) that you claim affects the runtime. Something is clearly amiss.
TheCoelacanth 8y ago
No, it's best-case O(1), worst-case O(n) (technically O(1) since there is a constant upper-bound, but let's pretend you said it's O(n) when length is divisible by 50 instead of equal to 50) and average-case O(1). Each of those functions has its own big O, without specifying which function you are talking about big O isn't meaningful.
- deleted 8y ago
  [deleted]

by roel_v 8y ago

deleted 8y ago

[deleted]

joshuamorton 8y ago

No, that algorithm is O(1). 50 is a constant. As n -> infinity, the algorithm runs in constant time. Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)). So I choose f(n) == 1, and C == 100. Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1, so it is O(1).

roel_v 8y ago
Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )
- joshuamorton 8y ago
  Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is). (If you reject that and claim that just because I can construct an algorithm that is O(1) from yours doesn't mean that your algorithm is O(1), I'll point out what you presented isn't technically a function, since its not mathematically pure, so the concept of Big-O is ill-formed)
  - roel_v 8y ago
    Well but (I think) what you're talking about now is the complexity of the 'wrapper' function I posed, not the complexity of the hypothetical algorithm I started out with. Yes you can add an indirection that converts it back into O(1) but the original, but that wasn't the point. I think. But then again, maybe what your second paragraph is saying is exactly that? I'll admit that I lost track of things somewhere between writing my original comment, switching back and forth to my code between compiles and now being back here :) Also, I don't understand what you mean by 'mathematically pure', but that's on my end.
    - robconery 8y ago
      The Big O of an algorithm does not change based on data size. Even if your set had precisely 1 record in it - the code you write, if it loops over every item in the set (even if it's only one item) - is still O(n).
      - roel_v 8y ago
        Yes I know that - was this reply meant for another comment?
    - joshuamorton 8y ago
      So there's two ways of looking at it, the more handwavy is "my construction that treats your algorithm as a black box does only ever strictly more work than your algorithm. If mine runs in a constant number of operations, yours must as well." And certainly your algorithm runs in amortized constant time (which is a weird phrase). The other way is to ask "what is a function"? Normally, a sorting function is expressed as sort(List[Comparable]) -> List[Comparable] your sorting function however has a different way of working. It has an additional input, the time. Now you might argue that you aren't taking the time as input, but you are...somehow. So in reality, your function has a signature sort(int, List[Comparable]) -> List[Comparable] There's this extra int input which is weird, so you don't have. Computational complexity tools like O-notation don't concern themselves with such things. O notation only cares about how the runtime changes as the size of the input changes. If the size of the int "time" is bounded (which it is, since the max is 86400), then one of the inputs is constant. It can be ignored. Purity in this context is the idea that the function only acts on its inputs, there are no external forces that modify how it works. Pure functions are mathematical objects, impure functions aren't really. So once you convert your construction to being pure, it becomes more clear why the function is ill-formed: you've got this extra constant size input (that runtime analysis can ignore) that you claim affects the runtime. Something is clearly amiss.

TheCoelacanth 8y ago

No, it's best-case O(1), worst-case O(n) (technically O(1) since there is a constant upper-bound, but let's pretend you said it's O(n) when length is divisible by 50 instead of equal to 50) and average-case O(1). Each of those functions has its own big O, without specifying which function you are talking about big O isn't meaningful.

deleted 8y ago
[deleted]