4 ms·

>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in th

by endtime 16y ago

>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. Once you start engineering things of course you have to take practical considerations into account (such as the classes of strings your algorithm is likely to be fed as input), but that doesn't invalidate (or devalue) proofs which make no claims about practical usage.

btilly 16y ago
>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios. This is absolutely not true. Big-O is a notation to describe the growth of functions. The functions themselves can describe anything you want, including either the average OR the worst case. The usage you complain about is therefore correct. See http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation for verification. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. It is actually a very unoriginal quip. I've been repeating it for years. Furthermore it is a quip with a lot of truth. Sciences are fields of study that use experiments to test hypotheses and refine theories. As you point out, CS is a lot like math, and unlike science, in that it is a field of knowledge which is in a large part based on our ability to construct ideas on top of each other and prove things about them rather than being built on experiment. In short "not science" is descriptive, not pejorative.
- endtime 16y ago
  >I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios... I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant: >A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.
  - deleted 16y ago
    [deleted]
  - plinkplonk 16y ago
    "Upper bound implies worst case." No it doesn't. You can talk about upper bounds on average case running time. The function under consideration can be any function, best case, worst case, average case, or any other function. O-notation is used to represent "asymptotic upper bound" on any function. (Omega-notation for lower bounds, Big Theta for simultaneous lower and upper bounds and so on, on any function). The upper or lower bounds of functions have nothing to do with the "case-iness" (best/worst/average running times etc) of algorithm running times. The "meaning" of the function (or for that matter the argument "n"), is completely orthogonal to its bounds. O(n) by itself does not say anything about what the function represents. The function does not have to be about algorithms. E.g: It could represent the error between an approximation and actual calculated value. You can use O notation to bound such functions, to state the upper bounds on the rate of growth of the error of an approximation. (Gilbert Strang uses O notation thus in his book "Calculus" for example). As another example, Knuth applies this notation to dozens of non-algorithm-running-time functions in Chapter 9 of Concrete Mathematics. Even when using such notation to discuss algorithm running times you really have to say O(n log_n) worst case (or best case or average case) running time for e.g, if you want to be clear. Thus (for example)from Cormen et al's "Introduction to Algorithms" book, emphasis mine (section 3.1 for anyone interested), "The Big_Theta(n^2) bound on the worst case running time of insertion sort does not imply a Big_Theta(n^2) bound on the running time of the insertion sort on every input.... when the input is already sorted insertion sort runs in Big_Theta(n) time" Big-Theta is applied to both best case and worst case running time functions in the above paragraph and the author clearly specifies what he is applying the bound to in each case. iow btilly is right (about how O notation can be used to represent any function, not just worst case running time functions) and you are wrong (when you say "Upper Bound implies worst case" ). As btilly states, this is a common misconception. Another common abuse of the notation is to use Big-Oh-notation when Big-Theta is intended.

by endtime 16y ago

>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. Once you start engineering things of course you have to take practical considerations into account (such as the classes of strings your algorithm is likely to be fed as input), but that doesn't invalidate (or devalue) proofs which make no claims about practical usage.

btilly 16y ago

>The IndexOf algorithm is also O(n) The author doesn't seem to understand big O. His indexOf approach is a linear algorithm in the average case, but not in the worst case - the author himself demonstrates this. I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios. This is absolutely not true. Big-O is a notation to describe the growth of functions. The functions themselves can describe anything you want, including either the average OR the worst case. The usage you complain about is therefore correct. See http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation for verification. >Computer Science (always suspect any discipline which feels the need to add the word 'science' to its name) is often an exercise in compromises. This kind of pissed me off, which was probably the intent. CS is about math, not implementation. It is actually a very unoriginal quip. I've been repeating it for years. Furthermore it is a quip with a lot of truth. Sciences are fields of study that use experiments to test hypotheses and refine theories. As you point out, CS is a lot like math, and unlike science, in that it is a field of knowledge which is in a large part based on our ability to construct ideas on top of each other and prove things about them rather than being built on experiment. In short "not science" is descriptive, not pejorative.

endtime 16y ago
>I suspect that you have the surprisingly common misconception that Big-O is about worst case scenarios... I appreciate what you're saying here, but I think this part of the Wikipedia page is relevant: >A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Upper bound implies worst case. I was going to say that big Theta is average case, but after some brief research I actually think I was mistaken on that.
- deleted 16y ago
  [deleted]
- plinkplonk 16y ago
  "Upper bound implies worst case." No it doesn't. You can talk about upper bounds on average case running time. The function under consideration can be any function, best case, worst case, average case, or any other function. O-notation is used to represent "asymptotic upper bound" on any function. (Omega-notation for lower bounds, Big Theta for simultaneous lower and upper bounds and so on, on any function). The upper or lower bounds of functions have nothing to do with the "case-iness" (best/worst/average running times etc) of algorithm running times. The "meaning" of the function (or for that matter the argument "n"), is completely orthogonal to its bounds. O(n) by itself does not say anything about what the function represents. The function does not have to be about algorithms. E.g: It could represent the error between an approximation and actual calculated value. You can use O notation to bound such functions, to state the upper bounds on the rate of growth of the error of an approximation. (Gilbert Strang uses O notation thus in his book "Calculus" for example). As another example, Knuth applies this notation to dozens of non-algorithm-running-time functions in Chapter 9 of Concrete Mathematics. Even when using such notation to discuss algorithm running times you really have to say O(n log_n) worst case (or best case or average case) running time for e.g, if you want to be clear. Thus (for example)from Cormen et al's "Introduction to Algorithms" book, emphasis mine (section 3.1 for anyone interested), "The Big_Theta(n^2) bound on the worst case running time of insertion sort does not imply a Big_Theta(n^2) bound on the running time of the insertion sort on every input.... when the input is already sorted insertion sort runs in Big_Theta(n) time" Big-Theta is applied to both best case and worst case running time functions in the above paragraph and the author clearly specifies what he is applying the bound to in each case. iow btilly is right (about how O notation can be used to represent any function, not just worst case running time functions) and you are wrong (when you say "Upper Bound implies worst case" ). As btilly states, this is a common misconception. Another common abuse of the notation is to use Big-Oh-notation when Big-Theta is intended.