4 ms·

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an

NO. BIG O notation is not average unless specified as such! It is an equivalence class of the provable upper bound on the execution time of the algorithm on an arbitrary input. There are algorithms like quick sort where average runtime != “big O of quicksort”

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).
- 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]
umanwizard 8y ago
This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothing to do with computation -- it's perfectly reasonable to say things like x^2 + 5x + 2 is O(x^2) and just be talking about pure math with no reference to algorithms). If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.
- enedil 8y ago
  To be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)
  - umanwizard 8y ago
    Sure, but that doesn't change my point.

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).
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]

umanwizard 8y ago

This is completely wrong. Big O has nothing to do with algorithms. Big O notation can be used for any mathematical function from an ordered set to another ordered set, including average runtime of an algorithm as a function of data size, worst-case runtime of an algorithm as a function of data size, guaranteed amortized runtime of an algorithm as a function of data size, or anything else (including things with nothing to do with computation -- it's perfectly reasonable to say things like x^2 + 5x + 2 is O(x^2) and just be talking about pure math with no reference to algorithms). If someone asked "what is the runtime of quicksort in big O terms", it is ambiguous whether the answer is O(n^2) or O(n*log(n)) , since it's not clear which function you're talking about.

enedil 8y ago
To be honest, this is false too. You need functions with values that can be multiplied by scalars. If you just have ordered set, then you can't account for this constant from the definition. Alternatively, you could say that values of the function need to be from a normed vector space (but I'm not sure if it can be extended furthermore. Maybe normed C-module?)
- umanwizard 8y ago
  Sure, but that doesn't change my point.