Let’s write a function which will find all duplicate elements and the number of repetitions in the given list using python. For example, function will return {11: 3, 1024: 2} for [11, 11, 23, 11, 1024, 66, 78, 1024] list.

## Solution 1

A = [11, 11, 23, 11, 1024, 66, 78, 1024] counter = {} for elem in A: counter[elem] = counter.get(elem, 0) + 1 doubles = {element: count for element, count in counter.items() if count > 1} print(doubles)

## Solution 2

A = [11, 11, 23, 11, 1024, 66, 78, 1024] from collections import Counter counter = Counter(A)

## Solution 3

A = [11, 11, 23, 11, 1024, 66, 78, 1024] from collections import defaultdict counter = defaultdict(int) for elem in A: counter[elem] += 1

## Complexity of Algorithm

The cost of compiling a counter list: you need to insert values into the dictionary n times. The insert consists of two operations: first, check to see if there is such a number in the dictionary and, in fact, the insert is all together O(1) average or O(n). So, the cost of compiling a counter is O(n) on average, O(n^2) at worst.

The next step is to filter only what you need. In the worst case, you need to go through the entire counter – again n operations on O(1) or in the worst O(n) – take from the dictionary, compare, write to a new dictionary. On average O(n).

Total O(n) on average or for specially prepared data O(n^2) at worst.