43

I was writing a python function that looked something like this

def foo(some_list):
   for i in range(0, len(some_list)):
       bar(some_list[i], i)

so that it was called with

x = [0, 1, 2, 3, ... ]
foo(x)

I had assumed that index access of lists was O(1), but was surprised to find that for large lists this was significantly slower than I expected.

My question, then, is how are python lists are implemented, and what is the runtime complexity of the following

  • Indexing: list[x]
  • Popping from the end: list.pop()
  • Popping from the beginning: list.pop(0)
  • Extending the list: list.append(x)

For extra credit, splicing or arbitrary pops.

1
  • Are you using pop or append anywhere? I don't see it. Indexing is O(1) so your code is already optimally efficient. What is bar doing?
    – ggorlen
    Jan 11, 2023 at 18:19

5 Answers 5

37

there is a very detailed table on python wiki which answers your question.

However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so:

for i, item in enumerate(some_seq):
    bar(item, i)
3
  • 1
    Forgive my ignorance, but where is the complexity for pop() on that page?
    – Zaz
    Oct 3, 2015 at 23:20
  • 2
    @Zaz, pop() with no index is O(1), with index, e.g. the first on list, it is O(n). since you need to get the item O(1) and then delete it. The latter takes O(n) time in order to arrange all the other items on the list. More on that here: ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt Oct 16, 2015 at 16:32
  • 1
    Indexing is O(1) so this answer is no more efficient from a complexity standpoint than OP's original code, although it's certainly cleaner. If OP has an efficiency problem, it's in the code they didn't show.
    – ggorlen
    Jan 11, 2023 at 18:19
8

The answer is "undefined". The Python language doesn't define the underlying implementation. Here are some links to a mailing list thread you might be interested in.

Also, the more Pythonic way of writing your loop would be this:

def foo(some_list):
   for item in some_list:
       bar(item)
1
  • Oops, I'm aware that my method was somewhat less than Pythonic. For my loop, I needed the item, as well as the index. Is there a good way to do that? (Editing my question) Jun 17, 2009 at 7:45
6

Lists are indeed O(1) to index - they are implemented as a vector with proportional overallocation, so perform much as you'd expect. The likely reason you were finding this code slower than you expected is the call to "range(0, len(some_list))".

range() creates a new list of the specified size, so if some_list has 1,000,000 items, you will create a new million item list up front. This behaviour changes in python3 (range is an iterator), to which the python2 equivalent is xrange, or even better for your case, enumerate

3

if you need index and value then use enumerate:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item
1

Python list actually nothing but arrays. Thus,

indexing takes O(1)

for pop and append again it should be O(1) as per the docs

Check out following link for details:

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.