On Wed, May 13, 2015 at 3:15 AM, Stefan Ram <r...@zedat.fu-berlin.de> wrote: > Rob Gaddi <rgaddi@technologyhighland.invalid> writes: >>Is that a true array or a linked list? "It's a high level language, >>that's just an implementation detail." Yes, but it's an implementation >>detail that determines whether even the simple act of looking up element >>n is O(1) or O(n). > > The complexity is given in the documentation of high-level languages. > > For example, from the documentation of the Java standard library: > > »This implementation provides constant-time performance > for the basic operations (get and put),« (java.util.HashMap) > > C++: > > Section 23.2.1 specifies the complexity, such as »compile time«, > »constant«, »linear« for container operations. > > But the abstraction mechanisms (templates, polymorphism) > often allow one to change the implementation quite easily.
It isn't always given in the docs. Sometimes it's not even a promise; back when MicroPython was debating the implementation of Unicode strings, there was a lengthy discussion on python-dev about whether it's okay for string subscripting to be O(n) instead of O(1), and the final decision was that yes, that's an implementation detail. (UTF-8 internal string representation, so iterating over a string would still yield characters in overall O(n), but iterating up to the string's length and subscripting for each character would become O(n*n) on uPy.) ChrisA -- https://mail.python.org/mailman/listinfo/python-list
