Can someone explain what this pseudo code is doing and math needed to get the ex

Question

Can someone explain what this pseudo code is doing and math needed to get the expected value.

Let rand(a,b) return an integer uniformly at random from the range [a, b]. Each call to rand(a,b) is independent. Consider the following function: f(k, n): if ks1 return rand(1, n) return 2 fs,n 2' What is the Expected value of f k, n), assume k is a power of 2. Please show your work. Beside the mathematical work, am expect 1-2 sentence that explain what the above pseudo code does and why your derivation is the right thing to do

Explanation / Answer

Expected value of f(k,n) is 'k' multiplied with a random number between '1 to n' i.e, k*rand(1, n)

k is a power of 2. so, assume k = 2p

when we call f(2p, n), result = 2*f(2p-1, n)

Then again result = 2*2*f(2p-2, n)

It will go like this till k becomes 1 i.e, 2p = 1, so p becomes 0. Hence by the time k becomes 1(p becomes 0), result will be k (2 multiplied p times i.e, 2p)

So when k will be 1, f() return random integer between 1 and n, Hence output will be k multiplied with a random number between 1 to n.

Example:

Take k = 8, n = 5

First call: f(8,5)

result = 2*f(8/2,5) = 2*f(4,5)

Second call: f(4,5)

result = 2*2*f(4/2,5) = 4*f(2,5)

Third call: f(2,5)

result = 4*2f(2/2.5) = 8*f(1,5)

Fourth call:

As k = 1, f() returns a random value between 1 and 5, assume it is 3

Hence result = 8*3 = 24

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---