Activity
#4849·Dennis Hackethal, 4 days ago"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.
I think I see now, and agree with the above. Partly a semantics issue (yes, I'm thinking of an algorithm in the "formal" CS sense: an abstract/mathematical finite procedure). The scare quotes were meant to suggest that one could attempt to implement one algorithm, but the implementation may in fact be more closely implementing some other unrelated algorithm, but this is confusing.
At any rate, how ChatGPT summarized it makes sense to me:
"One function → many algorithms can compute it.
One algorithm → many implementations can realize it.
Complexity attaches primarily to algorithms, secondarily to implementations, and not to functions."