Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is the [0]*n runs in O(n) or O(1) in Python [duplicate]

Tags:

python

big-o

Python What's the time complexity of using

a = [1]*n 

vs.

for i in range(n): 
    a.append(1)

Are both O(n) or does the first O(1)?

like image 352
Shimaa Avatar asked Nov 27 '13 22:11

Shimaa


1 Answers

The former is O(n), due to the use of PyList_New() with a known size. The latter is slightly worse than O(n), due to the need to resize the list after several appends.

like image 120
Ignacio Vazquez-Abrams Avatar answered Oct 02 '22 15:10

Ignacio Vazquez-Abrams