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

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