time complexity analysis
Time complexity analysis
Amortized analysis
Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster.
The example data structures whose operations are analyzed using Amortized Analysis are Hash Tables, Disjoint Sets and Splay Trees.
The complexity analysis using worst case gives a loose upper bound. Amortized analysis gives a tighter upper bound. In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of a particular expensive operation.
List operations
Inner working: Python lists are internally represented as arrays. The idea used is similar to implementation of vectors in C++ or ArrayList in Java. The costly operations are inserting and deleting items near the beginning (as everything has to be moved). Insert at the end also becomes costly if preallocated space becomes full.
| Operation | Examples | Amortized complexity |
|---|---|---|
| l.append(item) | O(1) |
| l.clear() | O(1) |
| in/not in l | O(N) |
| l.copy() | O(N) |
| del l[i] | O(N) |
| l.extend(…) | O(N) |
| l1==l2, l1!=l2 | O(N) |
| l[i] | O(1) |
| for item in l: | O(N) |
| len(l) | O(1) |
| k*l | O(k*N) |
| min(l), max(l) | O(N) |
| l.pop(-1) | O(1) |
| l.pop(item) | O(N) |
| l.reverse() | O(N) |
| l[x:y] | O(y-x) |
| l.sort() | O(N*log(N)) |
| l[i]=item | O(1) |
Deque
Deque is implemented using a doubly linked list inside. If you need to add/remove at both ends, consider using a collections.deque instead of list.
| Operation | Examples | Amortized complexity |
|---|---|---|
| l.copy() | O(1) |
| l.append() | O(1) |
| l.appendleft | O(1) |
| l.pop() | O(1) |
| l.popleft() | O(1) |
| l.extend(…) | O(K) |
| l.extendleft(…) | O(K) |
| l.remove(…) | O(n) |
Dictionary operations
| Operation | Examples | Amortized complexity |
|---|---|---|
| d.clear() | O(1) |
| dict(…) | O(len(d)) |
| del d[k] | O(1) |
| d.get() | O(1) |
| for item in d: | O(N) |
| len(d) | O(1) |
| d.pop(item) | O(1) |
| d.popitem() | O(1) |
| d.keys() | O(1) |
| d.fromkeys(seq) | O(len(seq)) |
Set operations
Inner working: Set in Python can be defined as the collection of items. In Python, these are basically used to include membership testing and eliminating duplicate entries. The data structure used in this is Hashing, a popular technique to perform insertion, deletion and traversal in O(1) on average. The operations on Hash Table are some what similar to Linked List. Sets in python are unordered list with duplicate elements removed.
| Operation | Examples | Amortized complexity |
|---|---|---|
| s.add(item) | O(1) |
| s.clear() | O(1) |
| s.copy() | O(N) |
| item in/not in s | O(1) |
| set(…) | O(len(s)) |
| s.discard(item) | O(1) |
| s1-s2 | O(len(s1)) |
| s1.difference_update(s2) | O(len(s2)) |
| s1==s2, s1!=s2 | O(min(len(s1), len(s2))) |
| s1 & s2 | O(min(len(s1), len(s2))) |
| for item in s: | O(N) |
| s1<=s2 | O(len(s1)) |
| s1>=s2 | O(len(s2)) |
| s.pop() | O(1) |
| s1 | s2 |
| s1^s2 | len(s1) |
Sorted container inner working
Inner implementation: http://www.grantjenks.com/docs/sortedcontainers/implementation.html
First impl intuition:
The first is that Python’s list is fast, really fast. Lists have great characteristics for memory management and random access.
The second is that bisect.insort is fast. This is somewhat counter-intuitive since it involves shifting a series of items in a list
Second impl intuition: But using only one list and bisect.insort would produce sluggish behavior for lengths exceeding ten thousand. So the implementation of Sorted List uses a list of lists to store elements. In this way, inserting or deleting is most often performed on a short list. Only rarely does a new list need to be added or deleted.
Compare with tree based impl
Traditional tree-based designs have better big-O notation but that ignores the realities of today’s software and hardware. For a more in-depth analysis, read Performance at Scale. Compared to tree-based implementations, using lists of lists has a few advantages based on memory usage.
Most insertion/deletion doesn’t require allocating or freeing memory. This can be a big win as it takes a lot of strain off the garbage collector and memory system.
Pointers to elements are packed densely. A traditional tree-based implementation would require two pointers (left/right) to child nodes. Lists have no such overhead. This benefits the hardware’s memory architecture and more efficiently utilizies caches.
The memory overhead per item is effectively a pointer to the item. Binary tree implementations must add at least two more pointers per item.
Iteration is extremely fast as sequentially indexing lists is a strength of modern processors.
SortedList operations
http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html
SortedSet operations
http://www.grantjenks.com/docs/sortedcontainers/sortedset.html
SortedDict operations
http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
References
Last updated
