# amortized analysis

a) define f(k) as the largest power of 2 that divides k. For example, f(25) = 1, f(42) = 2, f(144) = 16. What is ${1 \over k}\sum_1^k f(k)$?

b) define f(k) as the square of largest power of 2 that divides k. For example, f(25) = 1, f(42) = 4, f(144) = 256 What is ${1 \over k}\sum_1^k f(k)$?

c) define f(k) as the number of divisors of k. For example, f(25) = 3 (1,5,25), f(42) = 9 (1,2,3,6,7,12,14,21,42) What is ${1 \over k}\sum_1^k f(k)$?

-
Better not to reuse $k$ in ${1 \over k}\sum_1^k f(k)$. It is well-defined which are dummy and which are not, but it is harder to read. –  Ross Millikan Oct 13 '12 at 3:22
12 doesn't divide 42. –  Gerry Myerson Oct 13 '12 at 3:31
Amortized analysis? Really? –  Gerry Myerson Oct 13 '12 at 3:37
@GerryMyerson I agree I thought this was from financial problem. –  AD. Oct 13 '12 at 4:55
This is from Amortized Analysis. Amortized Analysis considers the cost for each step as the average of overall cost. –  CaptainObvious Oct 13 '12 at 5:44

For a, half the numbers are odd, so $f(k)$ is $1$, one quarter have a single factor of $2$ so f(k) is $2$, one eighth have two factors and so on. If we let the upper limit be a power of $2$, ${1 \over {2^m}}\sum_{k=1}^{2^m} f(k)=\frac 1{2^m} (\frac {2^m}2\cdot 1+\frac {2^m}4\cdot 2 + \frac {2^m}8\cdot 4 + \frac {2^m}{16}\cdot 8 \cdots )=\sum _{k=1}^{m} \frac 12=\frac m2.$ This will go to $\infty$ as $m \to \infty .$ A similar argument holds for b. For c you need to think about the prime number theorem
For a), you aren't using OP's definition. If $2^r$ exactly divides $k$, then $f(k)$ is $2^r$, not $r$. –  Gerry Myerson Oct 13 '12 at 3:34