On Tuesday, May 12, 2015 at 10:45:39 PM UTC+5:30, Stefan Ram wrote: > Rob Gaddi 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.
This is regarded in some circles as one of the big open problems in CS https://existentialtype.wordpress.com/2014/09/28/structure-and-efficiency-of-computer-programs/ [and the position paper therein] viz how to integrate the elegance of high-level languages with the precision of complexity analysis of machine language -- https://mail.python.org/mailman/listinfo/python-list
