Count occurence in a list with time complexity of O(nlogn)

Question

This is what I have so far:

alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
def icount(alist):
    adic={}
    for i in alist:
        adic[i]=alist.count(i)
    return adic

print(icount(alist))

I did some research to find out that the time complexity of list.count() is O(n), thus , this code will be O(n^2).

Is there a way to reduce this to O(nlogn)?

Answer 1

You can use Counter like this

from collections import Counter
alist=[1,1,1,2,2,3,4,2,2,3,2,2,1]
print Counter(alist)

If you want to use your solution, you can improve it like this

def icount(alist):
    adic = {}
    for i in alist:
        adic[i] = adic.get(i, 0) + 1
    return adic

Even better, you can use defaultdict like this

from collections import defaultdict
adic = defaultdict(int)
for i in alist:
    adic[i] += 1
return adic

Also, You might want to look at the Time Complexity of various operations on different Python objects here

Answer 2

Counter is your helper:

>>> from collections import Counter
>>> a = [1,2,1,3,4]
>>>  Counter(a)
Counter({1: 2, 2: 1, 3: 1, 4: 1})
>>> x = Counter(a)     
>>> x[1]
2
>>> x[2]
1

Get the count of each element easily through this method