|
You’re right, when a sort size depends on n, then it’s not considered O(1), I agree. > I don’t see why you think the addition involved in a comparison sort wouldn’t be O(1) Because you can’t have an infinite number of elements using 32-bit indices, you have to use indices that can represent up to n, and thus you must do arithmetic and comparsion operations on those indices that are not O(1). Considering that this was your original point, I’m totally confused why you’re now arguing against this point? It still seems inconsistent to me. Are you assuming that the size of the data elements to be sorted are 32 bits and that the only operations are on the data and not the indices? Bubble sort has to do both data comparisons and index comparisons, as well as index arithmetic. Adding 1 to a large n-bit number is worst case O(n). > The key difference for this project Euler example is that there the input n is actually an integer that we do the main artithmetic on. No, bubble sort has to do arithmetic on size n numbers too, as well as comparisons, the same as with Gauss’ formula. > then _any_ function I write whose only input is an int is O(1) and the notion is meaningless. No, this is both a straw-man and incorrect. A pure function on an int is only O(1) if it’s run-time doesn’t depend on the input. When the implementation is a constant number of 32-bit int operations on the input, and it doesn’t depend on what the value of the input is, then the function is O(1). Addition of two 32 bit ints on modern processors is O(1). Calculating whether an input int is prime, without having a lookup table in memory, for example, is not O(1), even though it’s a function of one 32-bit int. |