# How to count occurences in a Skiplist

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?

• Does the input set of elements contains repetitions or are they all distinct? Sep 13 at 9:11
• They can contain same elements and not a set! 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)$$.