CODEWITHSUNDEEP
algorithm
Aneesh Dogra
Aneesh Dogra

Reputation: 740

Cumulative frequency table with creation in linear or better than linear complexity?

I am trying to solve an algorithmic problem, and to solve it within the time constrains I need to implement a cumulative frequency table whose creation takes a linear or better than linear time? My inputs are integers only; hence, my keys of the frequency table are integers only. A simple implementation that I came up with is follows (assume cumulative_freq_table is a hashmap in the following code.):

read x
for key in range(x, N):
 if key in cumulative_freq_table:
  cumulative_freq_table[key] += 1

I haven't studied any algorithms related course, but I guess its complexity is around O(N^2). Can this be done in time better than O(N^2)?

Upvotes: 1

Views: 220

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

OFF-LINE APPROACH

If you are happy to use two passes then you can do this:

for each x:
  read x
  freq_table[x] += 1

t = 0
for key in range(0,N):
  t += freq_table[key]
  cumulative_freq_table[key] = t

This will be linear.

ON-LINE APPROACH

THe problem with the linear approach is that it requires all the data to be seen before you can access the cumulative frequency table.

There are alternative approaches that allow continual access to the cumulative frequency, but have higher complexity.

For example, have a look at Fenwick Trees for an approach that uses O(log(N)) operations for each element.

Upvotes: 2

Related Questions