Time Complexity to create a dictionary from a list in python-CodePudding

What would be the time complexity to create a dictionary for frequency of occurrence of elements in a list (in python)?

For example: I have a list - ls = [5,3,3,2] I want to create a dictionary to check frequency of each element in the list. This is the code for that:

freq = {}
for ele in ls:
    if ele in freq:
        freq[ele]  = 1
    else:
        freq[ele] = 1

This will create the dictionary from the list, but what would the time complexity be to create the dictionary?

Any insights on this would be helpful. Thank you.

CodePudding user response：

It would be linear O(n) complexity as you are only iterating through the list once with no nested loops/recursion/etc... As for checking ele in freq it is O(1) complexity as dicts are hash maps and using dict.__contains__ only does a hash lookup for the value. Although using collections.Counter is the more preferred way:

from collections import Counter

ls = [5,3,3,2]
freq = Counter(ls)

>>> dict(freq)
{5: 1, 3: 2, 2: 1}

CodePudding user response：

It should be linear O(n) because you are just looping from first to last of the list linearly.