3 ms·

I don't think the attitude of being allowed to be hand-wavey is a good one for this sort of thing. Big O notation has very precise semantics, and it is very eas

I don't think the attitude of being allowed to be hand-wavey is a good one for this sort of thing. Big O notation has very precise semantics, and it is very easily misused. Many of the examples are wrong. A python "print" statement is (for the built-in types at least) O(n), so printing the first item from a list must be at least O(n). Fundamentally, looking at big O notation as a way of measuring runtime is misguided. It is a way of describing a class of functions. But there is typically a level of indirection between the function that is being talked about, and the one which the analysis is applied to. For the "return the first item in the list" example, the function which is being analysed is a function from Int to Real. That function iterates through all values with size corresponding to the input to function, for each of these it runs the "return the first item in the list" function and measures the time it takes. The maximum time taken is then the Real output. That intermediate function is important, and needs to be specified properly. If it isn't, then you get confusion The section "N could be the actual input, or the size of the input" is an example of this confusion. Here, the intermediate function which is being analysed is much simpler (but it is still present). I should probably also add, that I am not by any means an expert here, and I wouldn't be surprised if I've made sloppy mistakes here. I'll just make the pre-claim that this only further proves my point that being hand-wavey is not a good thing :-)

scott_s 12y ago
When doing complexity analysis, one should state what the base operation is. For example, when looking at sorting algorithms, we typically use the operation "is x less than y?", or something similar to it. What the analysis then tells us is how many comparisons we make. The author does not state what his operations are. So, with regards to the examples, he implies that the operation he's counting is "print". So his examples are correct. You are right, though, that we can get in trouble if it turns out that our base operation - which we assume is constant time - is actually not constant time. When looking at algorithms that deal with very large numbers, for example, we can't consider multiplication to be constant time. So, with regards to the complexity of print, you are correct that it is linear - O(n) - in the item being printed. But I believe you are confusing the quantity "size of the list" and the quantity "size of an item in the list". If we have a list of size n, and that list contains items whose largest size is m, then we would say the cost of that first loop is O(n * m). If we can just assume that the size of an item is not large enough to matter - that is, m is actually a constant - then we can safely say that the cost is O(n).
- gameguy43 12y ago
  Agreed. I'm trying to strike a balance here between painting the full picture and being approachable for people who are scared of math. These notes are super helpful though--we can probably nod briefly to this complexity without getting /too/ stuck in the weeds. Really appreciate the thoughts!
ggchappell 12y ago
> Many of the examples are wrong. A python "print" statement is (for the built-in types at least) O(n), so printing the first item from a list must be at least O(n). Yes & no. Big-O is about counting something and seeing how that amount changes when our independent variable (input size, maybe) gets large. We can count whatever we want. It is correct to say that print(x) executes O(1) print statements. OTOH, it does not execute a constant number of single-character operations. > I don't think the attitude of being allowed to be hand-wavey is a good one for this sort of thing. Big O notation has very precise semantics, and it is very easily misused. That's a good point. Perhaps the best way to present big-O for "the masses" is (1) give people enough guidance to use it correctly, (2) make sure they know that this is not hand-wavey math, but rather one with precise definitions, but (3) not worry so much whether they know what those definitions are, or how to use them directly.

scott_s 12y ago

When doing complexity analysis, one should state what the base operation is. For example, when looking at sorting algorithms, we typically use the operation "is x less than y?", or something similar to it. What the analysis then tells us is how many comparisons we make. The author does not state what his operations are. So, with regards to the examples, he implies that the operation he's counting is "print". So his examples are correct. You are right, though, that we can get in trouble if it turns out that our base operation - which we assume is constant time - is actually not constant time. When looking at algorithms that deal with very large numbers, for example, we can't consider multiplication to be constant time. So, with regards to the complexity of print, you are correct that it is linear - O(n) - in the item being printed. But I believe you are confusing the quantity "size of the list" and the quantity "size of an item in the list". If we have a list of size n, and that list contains items whose largest size is m, then we would say the cost of that first loop is O(n * m). If we can just assume that the size of an item is not large enough to matter - that is, m is actually a constant - then we can safely say that the cost is O(n).

gameguy43 12y ago
Agreed. I'm trying to strike a balance here between painting the full picture and being approachable for people who are scared of math. These notes are super helpful though--we can probably nod briefly to this complexity without getting /too/ stuck in the weeds. Really appreciate the thoughts!

ggchappell 12y ago

> Many of the examples are wrong. A python "print" statement is (for the built-in types at least) O(n), so printing the first item from a list must be at least O(n). Yes & no. Big-O is about counting something and seeing how that amount changes when our independent variable (input size, maybe) gets large. We can count whatever we want. It is correct to say that print(x) executes O(1) print statements. OTOH, it does not execute a constant number of single-character operations. > I don't think the attitude of being allowed to be hand-wavey is a good one for this sort of thing. Big O notation has very precise semantics, and it is very easily misused. That's a good point. Perhaps the best way to present big-O for "the masses" is (1) give people enough guidance to use it correctly, (2) make sure they know that this is not hand-wavey math, but rather one with precise definitions, but (3) not worry so much whether they know what those definitions are, or how to use them directly.