Menu
I understand that a list is different from an array. But still, O(1)? That would mean accessing an element in a list would be as fast as accessing an element in a dict, which we all know is not true. My question is based on this document:
list ---------------------------- | Operation | Average Case | |-----------|--------------| | ... | ... | |-----------|--------------| | Get Item | O(1) | ----------------------------
and this answer:
Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure.
If the first document is true, then why is accessing a dict faster than accessing a list if they have the same complexity?
Can anybody give a clear explanation on this please? I would say it always depends on the size of the list/dict, but I need more insight on this.
955
Time Complexity for Append in Python This function has constant time complexity i.e. O(1), because lists are randomly accessed so the last element can be reached in O(1) time that's why the time taken to add the new element at the end of the list is O(1).
Lott: Insertion and removal are O(1) at any point in the list if you are already there (i.e. advancing along an element at a time using some sort of iterator). It's only if you want to first find some object to delete by some key, or to insert at some random location, that these operations become O(n).
The list index starts with 0 in Python. So, the index value of 1 is 0, 'two' is 1 and 3 is 2.
Why the complexity of fetching value is O(1)? As Arrays are allocated contiguously in memory, Fetching a value via an index of the array is an arithmetic operation. All arithmetic operations are done in constant time i.e., O(1).
Get item is getting an item in a specific index, while lookup means searching if some element exists in the list. To do so, unless the list is sorted, you will need to iterate all elements, and have O(n) Get Item operations, which leads to O(n) lookup.
A dictionary is maintaining a smart data structure (hash table) under the hood, so you will not need to query O(n) times to find if the element exists, but a constant number of times (average case), leading to O(1) lookup.
199
accessing a list l at index n l[n] is O(1) because it is not implemented as a Vanilla linked list where one needs to jump between pointers (value, next-->) n times to reach cell index n.
If the memory is continuous and the entry size would had been fixed, reaching a specific entry would be trivial as we know to jump n times an entry size (like classic arrays in C).
However, since list is variable in entries size, the python implementation uses a continuous memory list just for the pointers to the values. This makes indexing a list (l[n]) an operation whose cost is independent of the size of the list or the value of the index.
For more information see http://effbot.org/pyfaq/how-are-lists-implemented.htm
28
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
