If we have an sorted skiplist how can we count the occurences if it is sorted on a effective way? Occurence of the same element in the skiplist?

  • $\begingroup$ Does the input set of elements contains repetitions or are they all distinct? $\endgroup$ Sep 13 at 9:11
  • $\begingroup$ They can contain same elements and not a set! $\endgroup$
    – Jonte YH
    Sep 13 at 10:25

Suppose the skip list is constructed with probability parameter $p$. Suppose you want to find the number of occurrences of an element $e$ in the skip list.

Algorithm: Perform a standard search of $e$ in the skip list. Suppose, the element is found at level $i$. Then, the element must also appear in each of the levels from $1$ to $i$ since a level $j$ is a subset of level $i$ if $j < i$.

To count the number of occurrences of the element at any such level, the algorithm makes a linear scan to left and right from the current position. Since each level is sorted, the algorithm stops once it finds an element different from $e$. This takes time $O(p_j)$, where $p_j$ is the number of occurrences of element $e$ at $j^{th}$ level.

Overall time is: search time + $\sum_{j = 1}^{i} O(p_j)$ = search time + $p_{e}$, where $p_e$ is the total number of occurrences of element $e$ in the skip list.

If the element $e$ has $t$ copies in the input set, then the expected number of times it appears in the skip list is $t /p$. That is $\mathbb{E}[p_e] = t/p$. Also, the expected search time in a skip list is $O(\frac{1}{p} \cdot \log_{1/p} n)$. Therefore, the overall search time becomes $O(\frac{1}{p} \cdot \log_{1/p} n) + O(t/p)$.


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.