Jan-10-2019, 07:33 AM
Quote:My suggested implementation from the previous thread:I think this program is not of complexity O(n); You have assumed that
sequence = 48,52,55,48,52,55,60,62,48 result = [] cum_count = {} for num in sequence: cum_count[num] = cum_count.get(num, 0) + 1 result.append(cum_count[num]) print(result)
Output:[1, 1, 1, 2, 2, 2, 1, 1, 3]
dict.get(num,0)is of constant complexity. However this is not the case; The get method has to go through the dictionary keys every time it is called. Your code has a worst case complexity of O(n^2). Correct me if I'm wrong