{"id":113211,"date":"2020-05-21T13:06:18","date_gmt":"2020-05-21T13:06:18","guid":{"rendered":"https:\/\/blog.finxter.com\/?p=8723"},"modified":"2020-05-21T13:06:18","modified_gmt":"2020-05-21T13:06:18","slug":"runtime-complexity-of-python-list-methods-easy-table-lookup","status":"publish","type":"post","link":"https:\/\/sickgaming.net\/blog\/2020\/05\/21\/runtime-complexity-of-python-list-methods-easy-table-lookup\/","title":{"rendered":"Runtime Complexity of Python List Methods [Easy Table Lookup]"},"content":{"rendered":"

What’s the runtime complexity of various list methods? <\/strong><\/p>\n

The following table summarizes the runtime complexity of all list methods.<\/p>\n

Assume that the length of the data type is defined as n<\/code> (that is—len(data_type)<\/code>). You can now categorize the asymptotic complexity of the different complexity functions as follows:<\/p>\n

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Operation<\/th>\nExample<\/th>\nComplexity<\/th>\n<\/tr>\n<\/thead>\n
Index<\/a><\/td>\nl[i]<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Store<\/a><\/td>\nl[i] = 42<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Length<\/a><\/td>\nlen(l)<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Append<\/a><\/td>\nl.append(42)<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Pop<\/a><\/td>\nl.pop()<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Clear<\/a><\/td>\nl.clear()<\/code><\/td>\nO(1)<\/em><\/td>\n<\/tr>\n
Slicin<\/a>g<\/a><\/td>\nl[a:b]<\/code><\/td>\nO(b-a)<\/em><\/td>\n<\/tr>\n
Extend<\/a><\/td>\nl1.extend(l2)<\/code><\/td>\nO(len(l1)+len(l2))<\/em><\/td>\n<\/tr>\n
Constructor<\/a><\/td>\nlist(iter)<\/code><\/td>\nO(len(iter))<\/em><\/td>\n<\/tr>\n
Equality<\/a><\/td>\nl1 == l2<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Slice Assign<\/a><\/td>\nl[a:b] = ...<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Delete<\/a><\/td>\ndel l[i]<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Remove<\/a><\/td>\nl.remove(...)<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Membership<\/a><\/td>\nx in l \/ x not in l<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Copy<\/a><\/td>\nl.copy()<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Pop<\/a><\/td>\nl.pop(0)<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Min<\/a><\/td>\nmin(l)<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Max<\/a><\/td>\nmax(l)<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Reverse<\/a><\/td>\nl.reverse()<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Iterate<\/a><\/td>\nfor x in l:<\/code><\/td>\nO(n)<\/em><\/td>\n<\/tr>\n
Sort<\/a><\/td>\nl.sort()<\/code><\/td>\nO(n log(n))<\/em><\/td>\n<\/tr>\n
Multiply<\/a><\/td>\nl*k<\/code><\/td>\nO(n k)<\/em><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n

Need to learn more about these methods? Watch me giving you a quick overview of all Python list methods:<\/p>\n

\n
\n