 |
.. (לתיקייה המכילה) | |
Can I implement a Skiplist for this exercise ? | |
|
In a random Skiplist data structure the expected insertion/deletion/find complexity is O(log n ). In a deterministic Skiplist data structure the worst-case insertion/deletion/find complexity is O(log n ). This data structure is basically a "2-3 tree" with linked-lists in each level. The time complexity constraint for this exercise is worst-case, therefore, a random Skiplist is NOT suitable. However, a deterministic Skiplist or a "2-3 tree" are eligible. |
What is the space complexity of recursions? | |
|
The space complexity recursive procedure is the depth of the recursion. For example a recursive find on an AVL-tree will take O(log n) space. In this exercise the space requirement is O(1) for all function, therefore, a recursive implementation is not an option. |