I assume my array sort won't be n^3, but how do we draw the line on what to assume and what not to assume?
I assume my array sort won't be n^3, but how do we draw the line on what to assume and what not to assume?
[1] https://en.wikipedia.org/wiki/Timsort
[2] https://svn.python.org/projects/python/trunk/Objects/listsor...
I mean a guarantee that it meets some baseline efficiency that you can depend on across time and different implementations. Does that exist?
To draw the line on what you can assume re performance, you need a combination of background knowledge, folk wisdom and common sense. (You could say "or read the code" but that could change in the next minor version: you still need common sense to know if that's likely). This is unlike, e.g. C++ where there is a specification and standards-compliant compilers must implement certain functions with the specified runtime complexity.
[0] https://docs.python.org/3/reference/introduction.html#altern...
If builtin, then you'll need to check the code for cpython or whatever you're using.