What is "amortized number"?

Question

I couldn't understand this question, could someone who knows about this issue show me the solution?

Priest Francis, responsible for ringing the bells, made a device that rings the bells automatically. At every exact hour, the device rings at least 1 of the n bells. Specifically, the i-th bell rings every 1 hour. For example, suppose that n = 4 and that Father Francisco turned on his device just after midnight. The ringing scheme of the bell is shown below. What is the amortized number of bells ringing per hour as a function of n?

Answer 1

To get amortized complexity, you find the complexity in terms of the average cost over a sequence of operations, rather than taking the complexity naively as the worst case for a single operation times the number of operations.

Applied to this case, without amortization you could take the complexity as the worst case for a single hour (all n bells could ring), times the number of hours (you didn't specify, so I'll assume it's a variable, h). In this way, we would get O(nh) total bells being run with O(n) bells being rung in any given hour. However, all n bells ring so infrequently (specifically, only every n! hours), that maybe with amortization we can do better.

We then aim to get the amortized number of bells rung per hour as the total number of bells rung over all h hours, T(n,h), divided by h. To derive this total sum, note that Bell1 will ring h times, Bell2 will ring h/2 times, Bell3 h/3 times, and so on. T(n,h) is then given by the sum:

T(n,h) is h times the harmonic series up to n, so we can represent it as hH(n), where H(n) denotes the nth harmonic number. This mean the amortized complexity for a single hour, as the total number of bells rung divided by the number of hours, is H(n).

It is known that H(n) is approximated by ln(n) as n goes to infinity (essentially because H(n) is approximately the integral of 1/x dx = ln(n)), so the amortized complexity, in terms of the average number of bells being rung per hour, is O(ln(n)) = O(logn).