0
$\begingroup$

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)$?

  • 0
    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.2012-10-13
  • 0
    12 doesn't divide 42.2012-10-13
  • 0
    Amortized analysis? Really?2012-10-13
  • 0
    @GerryMyerson I agree I thought this was from financial problem.2012-10-13
  • 0
    This is from Amortized Analysis. Amortized Analysis considers the cost for each step as the average of overall cost.2012-10-13

1 Answers 1