algorithm - Approximate count of events over given time frame -

i have efficient way of calculating (approximate) count of recurring event on given time frame.

example: trying repeatedly download file host. works fine, error happens when network congested. don't care these single errors. every once in while though, host offline, attempts fail. in case automatically stop program trying again.

so need find out how many errors occured on last x minutes. when number below threshold, nothing happens. when above, want take action. count not have 100% accurate, accurate enough tell me whether threshold reached.

a simple, yet ineffective (o(n)), way of doing store timestamps of events, , every new event determine number of previous events iterating on them , comparing timestamps (up until time frame reached). [aside] imagine sql engines where timestamp between now() , interval x minutes, unless have index on column. [/aside]

i want solution constant (o(1)) complexity. far thinking keep counter of event increases 1 every event. store timestamp of recent occurance. then, when new event happens, math magic can decrease counter using current time , stored timestamp reflect approximately how many events happened on last x minutes.

unfortunately math skills not task. can provide hints?

if you're going threshold failure count within last x minutes, why not store failure timestamps in circular buffer of capacity equal threshold? inserts o(1), , check whether there have been enough failures, test whether least inserted timestamp within last x minutes.