How does Python find the length of the array? Is it stored somewhere in an internal data-structure or does it have to iterate through the entire thing to find the length?
I ask because I'm using it for a binary search which should run in O(log(n)), but this obviously doesn't make sense if I have to iterate through the whole thing just to find the length.
asked Jun 7, 2016 at 3:38
Alexander Kleinhans
6,32814 gold badges67 silver badges122 bronze badges
-
2wiki.python.org/moin/TimeComplexityfalsetru– falsetru2016年06月07日 03:40:15 +00:00Commented Jun 7, 2016 at 3:40
-
For list is O(1), other types look here: ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txtSerenity– Serenity2016年06月07日 03:41:37 +00:00Commented Jun 7, 2016 at 3:41
1 Answer 1
Lists can store their length as part of their structure. Since it only needs to be stored in one place, it can add a maximum of O(1) to all computations and therefore not be too much overhead.
Getting the length is therefore O(1) because it's just the lookup of a field.
For more information, see the docs.
answered Jun 7, 2016 at 3:50
k_g
4,4932 gold badges28 silver badges40 bronze badges
Sign up to request clarification or add additional context in comments.
Comments
lang-py