time complexity improv of frequencies.md

[gurukiran07]

In frequencies.md, the time complexity is O(n^2). list.count()'s complexity is O(n), using list.count n times, making it quadratic time.

# Current implementation.
def frequencies(lst):
  return dict((k, lst.count(k)) for k in lst)

We can use collections.Counter which does it in O(n).

from collections import Counter
def frequencies(lst):
    return Counter(lst)

Using collection.defaultdict

from collections import defaultdict
def frequencies(lst):
    d = defaultdict(int)
    for v in lst:
        d[v]+=1
    return d

# pure python implementation
def frequencies(lst):
    d = dict()
    for v in lst:
        d[v] = d.get(v, 0) + 1  # d.setdefault(v, 0)
    return d

All the above mentioned are O(n) run time functions. Please select whichever you see fit.

[Trinityyi]

That's an accurate observation. Counter might be a bit too much of a black box for some readers, but you might be onto something with the defaultdict implementation. Only thing I'd change in that one would be the return statement to wrap the result in a dict() call. Other than that, I think that's a valid way to improve the snippet, so feel free to PR it.

[Navaneethnanda]

really great improvement

[gurukiran07]

Counter might be a bit too much of a black box for some readers @Trinityyi

Yes, agreed.

Only thing I'd change in that one would be the return statement to wrap the result in a dict() call

Okay, will do.

And I made a partial list of questions(will prepare the whole list in a day or two) that are frequently asked on StackOverflow, should I post the list in another issue where we can scrutinize the proposed questions?

[Chalarangelo]

@gurukiran07 Sure, you can open an issue and we might start tackling them one by one.