Menu
I'm referring to this: http://docs.python.org/tutorial/datastructures.html
What would be the running time of list.index(x) function in terms of Big O notation?
624
The index() method has linear runtime complexity in the number of list elements. For n elements, the runtime complexity is O(n) because in the worst-case you need to iterate over each element in the list to find that the element does not appear in it.
@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.
Hence, len() function in Python runs in O(1) complexity.
the time complexity of slicing in python is O(k) please visit https://wiki.python.org/moin/TimeComplexity#list for more.
It's O(n), also check out: http://wiki.python.org/moin/TimeComplexity
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n)...
185
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
