[Python] Why is using a dictionary slower than sorting a list to generate frequency array?

I was doing this question on Codeforces (2057B - Gorilla and the Exam) where I had to use the frequencies of different numbers in a list. First I tried calculating it with a dictionary but I got TLE verdict (Time limit exceeded). After reading the editorial I implemented it by sorting the input list and then using comparisons with the previous element to generate the frequency array. This was faster than the approach using the dictionary but sorting is an O(nlogn) operation which should take more time than creating a dictionary which only requires O(n) time.

Dictionary approach (slower)

t= int(input())
for _ in range(t):
n, k = map(int, input().split())
arr = map(int, input().split())
frequence_table = {}
for num in arr:
try:
frequence_table[num] += 1
except:
frequence_table[num] = 1
freq = list(frequence_table.values())
freqs = sorted(freq, reverse=True)
while k>0:
if k>=freqs[-1]:
k -= freqs.pop()
else:
break
print(max(len(freqs), 1))


Sorting based approach (faster)

t= int(input())
for _ in range(t):
n, k = map(int, input().split())
arr = map(int, input().split())
arr = sorted(arr)
freq = [1]
for i in range(1, len(arr)):
if arr == arr[i-1]:
freq[-1] += 1
else:
freq.append(1)
freqs = sorted(freq, reverse=True)
while k>0:
if k>=freqs[-1]:
k -= freqs.pop()
else:
break
print(max(len(freqs), 1))

Continue reading...