Activity
#4848·Tyler MillsOP, about 23 hours ago"Complexity" in the sense of growth behavior with input size? Further reading is still suggesting to me that this is intrinsic to a given algorithm (or class of them). Intrinsic to the math and logic. Implementations can be faster/slower/hungrier for a given input, but if they have different limiting behavior, aren't they different algorithms? I can see how an "implementation" of one algorithm in practice can accidentally change it to another algorithm.
"Complexity" in the sense of growth behavior with input size?
Yes.
I can see how an "implementation" of one algorithm in practice can accidentally change it to another algorithm.
Not sure why you put that in scare quotes. You might be right in the CS sense where ‘algorithm’ refers to an abstract procedure whereas ‘implementation’ is concrete code realizing that algorithm. (Though as a disclaimer, I don’t have a CS degree. My experience with programming is fully on-the-job.)
My point is more that two different implementations that compute the same function can have different big O. In that case, they’re usually considered different algorithms, even if the high-level goal is the same.
Regardless, the structure of the program is by far the most important factor determining performance characteristics. If you were saying that complexity is independent of implementation only insofar as the implementation truly implements the same algorithm, then I agree. So I’m not sure whether I should mark this as a counter-criticism. For now I won’t, pending new evidence.