Is exectution time of Skip list different after every run for same input?

Question

I know this question is quiet trivial but I am curious to understand about what is actual impact on execution time of skip list algorithm that is randomized algorithm on time of execution.

Are they different at every run?

If they are is this one of the reaason why this algorithm is randomized?

And if they are then can we conclude that randomisation algorithm randomize the time of execution as well?

Answer 1

So, the main question here is what are the operations you want to perform on the skip list.

1. Suppose, let's say you have an existing skip list and you just wish to search a few elements in it.

   The search algorithm is not randomized. Although it depends on the total number of levels, it is advised to keep them at O(log n) for effective performance.

   So, for a static skip list, the search execution time would be the same.

2. If you have a set of numbers and you want to create a skip list and then do certain operations

   Now, the lowest level would be the entire sorted linked list. However, the next level is determined with the help of a coin toss(randomized).

   Here, there is no guarantee that the skip list constructed would be the same after multiple runs. So, the search time would differ as well.

But the overall time complexity(Amortized) remains the same.

The reason why it is randomized is to handle performance. If we think of a static way to create the levels, then there would definitely be a worst-case input that affects the time complexity. Even with randomness, this is possible, but the idea is that the probability of it happening is very less. And that's why randomized algorithms are effective.