Cost Of List Functions In Python

Based on this older thread, it looks like the cost of list functions in Python is: Random access: O(1) Insertion/deletion to front: O(n) Insertion/deletion to back: O(1) Can anyo

Solution 1:

Take a look here. It's a PEP for a different kind of list. The version specified is 2.6/3.0.

Append (insertion to back) is O(1), while insertion (everywhere else) is O(n). So yes, it looks like this is still true.

Operation...Complexity
Copy........O(n) 
Append......O(1)
Insert......O(n) 
Get Item....O(1)
Set Item....O(1)
Del Item....O(n) 
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k) 
Sort........O(n log n)
Multiply....O(nk)

Solution 2:

Python 3 is mostly an evolutionary change, no big changes in the datastructures and their complexities.

The canonical source for Python collections is TimeComplexity on the Wiki.

Solution 3:

That's correct, inserting in front forces a move of all the elements to make place.

collections.deque offers similar functionality, but is optimized for insertion on both sides.

Solution 4:

I know this post is old, but I recently did a little test myself. The complexity of list.insert() appears to be O(n)

Code:

'''
Independent Study, Timing insertion list method in python
'''import time

defmake_list_of_size(n):
    ret_list = []
    for i inrange(n):
        ret_list.append(n)
    return ret_list

#Estimate overhead of timing loopdefget_overhead(niters):
    '''
    Returns the time it takes to iterate a for loop niter times
    '''
    tic = time.time()
    for i inrange(niters):
        pass#Just blindly iterate, niter times
    toc = time.time()
    overhead = toc-tic
    return overhead

deftictoc_midpoint_insertion(list_size_initial, list_size_final, niters,file):
    overhead = get_overhead(niters)
    list_size = list_size_initial
    #insertion_pt = list_size//2 #<------- INSERTION POINT ASSIGMNET LOCATION 1#insertion_pt = 0 #<--------------- INSERTION POINT ASSIGNMENT LOCATION 4 (insert at beginning)
    delta = 100while list_size <= list_size_final:
        #insertion_pt = list_size//2 #<----------- INSERTION POINT ASSIGNMENT LOCATION 2
        x = make_list_of_size(list_size)
        tic = time.time()
        for i inrange(niters):
            insertion_pt = len(x)//2#<------------- INSERTION POINT ASSIGNMENT LOCATION 3#insertion_pt = len(x) #<------------- INSERTION POINT ASSIGN LOC 5 insert at true end
            x.insert(insertion_pt,0)
        toc = time.time()
        cost_per_iter = (toc-tic)/niters #overall time cost per iteration
        cost_per_iter_no_overhead = (toc - tic - overhead)/niters #the fraction of time/iteration, #without overhead cost of pure iteration                                              print("list size = {:d}, cost without overhead = {:f} sec/iter".format(list_size,cost_per_iter_no_overhead))
        file.write(str(list_size)+','+str(cost_per_iter_no_overhead)+'\n')
        if list_size >= 10*delta:
            delta *= 10
        list_size += delta

defmain():
    fname = input()
    file = open(fname,'w')
    niters = 10000
    tictoc_midpoint_insertion(100,10000000,niters,file)
    file.close()

main()

See 5 positions where insertion can be done. Cost is of course a function of how large the list is, and how close you are to the beginning of the list (i.e. how many memory locations have to be re-organized)

Ignore left image of plot

Solution 5:

Fwiw, there is a faster (for some ops... insert is O(log n)) list implementation called BList if you need it. BList