Implemented: Rahul Manghwani. NYU Courant

Notes Based on lecture by Professor Prof. Erik Demaine. MIT at OCW.

Skiplist - A Probabilistic Data Structure for Ordered Sets

Complexity

Search,Insert and Delete  - 0(logn) with very high probability


Probability of a Success of a Event like Search happening in log(n) is given by 1 - (1/n^alpha) for any alpha>=1.

1/n^alpha is called error probability. For a suitable alpha like 100. this probability is very less. This is affected in constant with log term 
but time is still logarithmic.

Important: This is only true if we perform such events(search,update,delete) polynomial no of times. Above that logn Complexity does not hold.