1
$\begingroup$

I have come across this video on skip lists:

https://www.youtube.com/watch?v=UGaOXaXAM5M

Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm. But I am confused: is it a Las Vegas algorithm or a Monte Carlo algorithm?

I feel it is a Monte Carlo algorithm since there is a possiblity of an incorrect output(degenerate case where every node is in every level), and if we don't maintain a checking condition, we won't know where the algo went wrong.

Am I correct?

P.S. My first question here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The difference between a Las Vegas algorithm and a Monte Carlo algorithm is that a Las Vegas algorithm is always correct but its running time may be large with small probability, whereas a Monte Carlo algorithm always has the same time complexity but may give wrong results with small probability.

These definitions are more appropriate for decision problems and optimization problems, and less for data structures. That said, they still make sense for data structures. Here are two examples:

  • Skip-lists correctly implement the list abstract data type. They are efficient with high probability. This is like a Las Vegas algorithm.
  • Bloom filters are always efficient (in this case we care about space complexity), but may give wrong results to queries. This is like a Monte Carlo algorithm.

Most data structures are designed with the Las Vegas objective in mind.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "Skip lists always conform to the specifications." Could you please elaborate what do you mean by specifications? Also, thank you so much for the answer. $\endgroup$
    – Ricky
    Feb 7, 2021 at 11:58
  • $\begingroup$ Skip lists are an implementation of the list data structure. As a user, they just behave as expected. If you insert an element, it gets inserted. If you search for an element, it gets searched. You seem to be confusing the specification of a data structure with its implementation. $\endgroup$
    – Yuval Filmus
    Feb 7, 2021 at 12:01
  • $\begingroup$ Looks like I found what I was looking for. Thank you. $\endgroup$
    – Ricky
    Feb 7, 2021 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.