sum(1/n) grows as O(log n)
sum((log n)/n) grows as O((log n)^2)
sum((log n)^c/n) grows as O((log n)^(c+1))
sum(1) grows as O(exp(log n)) = O(n)
next, faster than any constant power of logarithm but slower than linear:
sum(1/(sqrt n)) grows as O(sqrt n)
sum(1/n^(1-delta)) grows as O(n^delta) for constant delta > 0. more precisely, integral(1/x^(1-delta), x from 1 to n) = (n^delta - 1)/delta. as delta gets smaller, the constant factor gets larger.
all of these derived by substituting integral for sum.
motivation is reward for a game: n units of work result in unbounded but less than linear reward, e.g. weapon multiplier.
one can play tricks by starting the series not at n=1, by taking steps not of size 1, or multiplying by a constant.
previously, growing slower than harmonic. this would be very frustrating for a game (future post kybzoejv).
No comments :
Post a Comment