[Pseudocode] [Advanced Algorithm] Improving Efficiency

I was originially given the following algorithm and asked to make it more efficient. I have provided additional comments that also might help. The questions are on the bottom, please read all the information before attempting them

The improved "FindFake3" effiencient algorithm is given below (Please check if it is more efficient compared to the one on top).

Findfake3(coinpile, n) if n=1 return the first coin in coinpile if n=2 and weight of coin1 > weight of coin2 then return coin2 else return coin1 thirdn = n div 3 pile1 = 1/3rd of the first coins in coinpile pile2 = 1/3rd of the next coins in coinpile pile3 = 1/3rd of the last coins in coinpile compareweight = Weigh(pile1,pile2,pile3); if compareweight = 1 return Findfake3(pile1,thirdn) if compareweight = 2 return Findfake3(pile2,thirdn) if compareweight = 3 return Findfake3(pile3,thirdn) return Findfake(last 2 coins of coinpile,2) //Weigh(coinpile1, coinpile2, coinpile3) returns: //0 if all 3 coinpiles have equal weight //1 if coinpile2 and coinpile3 weigh the same //2 if coinpile1 and coinpile3 weigh the same //3 if coinpile1 and coinpile2 weigh the same

The question are as follows:

a) Set up a recurrence relation for C3(n) = the number of weighings for the Findfake3 algorithm and solve it for n = 3^k

b) For large values of n, how much faster is the Findfake3 algorithm than the Findfake2 algorithm? Explain your answer mathematically. Your answer should not depend on n. (Hint: look up how to change bases in logarithms)

c) What is C3(n) in the best case? explain your answer.

PLEASE provide detailed answers for the following with explanation if required. Thank you

Pseudocode for Findfa The algorithm above can be described in pseudocode as follows: Findfake2 ile n) returns coin. Coin is a data structure representing coins coinpile is a Collection of Coins n is the size of coinpile It is known that there is one fake coin in coinpile Findfake2 (coinpile, n) if n 1 return the first coin in coinpile halfn n div 2 pilel Collection of coins consisting of the first halfn elements of coinpile pile2 Collection of coins consisting of the next halfn elements of coinpile compareweight Weigh (pile 1, pile2) if compareweight 1 return Find fake2 (pilel halfn) if compareweight 1 return Findfake2 (pile2, halfn return nth coin in coinpile Weigh (coinpilel, coinpile2 returns -1 is coinpilel weighs less than coinpile2 0 if coinpilel and coinpile 2 weigh the same 1 is coinpilel weighs more than coinpile2 Additional Information 1. The size of the problem is n of coins in coinpile 2. The basic operation is a function call to the Weigh function 3. The best case scenario is when n s odd and the fake coin is the last coin of the coinpile collection. In that case Weigh will only be called once and therefore Findfake2 is O n the best case. 4. The worst case scenario is when the decision is only made when weighing two coins against each other after all the other c have been discarded (except possibly for a third one if 3 in the last function call) In this case, since Findfake2 is recursive, we need to set up a recurrence relation for its cost, as follows: Let C(n) Hof times the function Weigh is called when coinpile had n elements C (1) 0: C(n) 1+C(floor (n/2)) if n 1 This recurrence relation is more or less the same as the one we saw in the algorithm to find the binary representation of an integer, and also in the binary search algorithm. The difference is in the starting condition As in these two algorithms, the recurrence relation is solved by first assuming that floor (n/2) n/2 at each step. In other words that n 2k from some k. i.e. k log2n This changes the recurrence relation to C (20) 0, C(2 C(2 if k>0 k-2 k-3 k-k Substituting back into the recurrence relation, you get C(n C (2 C(2 C(2 +1+1+C(2 k+C (2 k C(2 Pseudocode for Findfa The algorithm above can be described in pseudocode as follows: Findfake2 ile n) returns coin. Coin is a data structure representing coins coinpile is a Collection of Coins n is the size of coinpile It is known that there is one fake coin in coinpile Findfake2 (coinpile, n) if n 1 return the first coin in coinpile halfn n div 2 pilel Collection of coins consisting of the first halfn elements of coinpile pile2 Collection of coins consisting of the next halfn elements of coinpile compareweight Weigh (pile 1, pile2) if compareweight 1 return Find fake2 (pilel halfn) if compareweight 1 return Findfake2 (pile2, halfn return nth coin in coinpile Weigh (coinpilel, coinpile2 returns -1 is coinpilel weighs less than coinpile2 0 if coinpilel and coinpile 2 weigh the same 1 is coinpilel weighs more than coinpile2 Additional Information 1. The size of the problem is n of coins in coinpile 2. The basic operation is a function call to the Weigh function 3. The best case scenario is when n s odd and the fake coin is the last coin of the coinpile collection. In that case Weigh will only be called once and therefore Findfake2 is O n the best case. 4. The worst case scenario is when the decision is only made when weighing two coins against each other after all the other c have been discarded (except possibly for a third one if 3 in the last function call) In this case, since Findfake2 is recursive, we need to set up a recurrence relation for its cost, as follows: Let C(n) Hof times the function Weigh is called when coinpile had n elements C (1) 0: C(n) 1+C(floor (n/2)) if n 1 This recurrence relation is more or less the same as the one we saw in the algorithm to find the binary representation of an integer, and also in the binary search algorithm. The difference is in the starting condition As in these two algorithms, the recurrence relation is solved by first assuming that floor (n/2) n/2 at each step. In other words that n 2k from some k. i.e. k log2n This changes the recurrence relation to C (20) 0, C(2 C(2 if k>0 k-2 k-3 k-k Substituting back into the recurrence relation, you get C(n C (2 C(2 C(2 +1+1+C(2 k+C (2 k C(2