2 ms·
>Why is this hard? In Clojure, the complexity of all core functions is well defined. i.e. map is O(n), hash lookups are log_32(n) or better, etc. Seems like you
by eli_gottlieb 15y ago
>Why is this hard? In Clojure, the complexity of all core functions is well defined. i.e. map is O(n), hash lookups are log_32(n) or better, etc. Seems like you can compute the complexity analysis at compile time.
Because your standard for-loop iterating through a collection is a special case of all for-loops. Much old code doesn't even use iterator-based or comprehension-based for-loops, but instead just iterates through arrays by using a local variable as an index.
for(int i=0;i<strlen(string);i++)
The programmer knows that strlen() will return the length of the null-terminated string string, but without dependent types or some similar computation, the compiler has no idea. To your C compiler, that string is just another pointer to a character!
If we "move up" to a language like Java or C++ where iteration uses (gasp) iterators, then we have to detect the special case of code employing an iterator class/type and associate a collection-size variable n with the collection over which we're iterating.
I say special case because that check will only catch the employment of an iterator via an iterator-based for loop, not a while loop. And the while loops or index-based for iterations can also have off-by-one errors and other bugs that will, needless to say, prevent our static complexity analysis from proceeding as planned.
These things look easy to analyze to the human eye because Pseudocode is the Sufficiently Smart Language, designed by humans for performing complexity, computability and correctness proofs. Once we get actual code involved, any resemblance to our vaunted Pseudocode is a happy coincidence.