This is a Discrete math question I understand the algorithm

This is a Discrete math question. I understand the algorithm but I want to figure out C(n) = \"some function of n\" formula. Please show steps and calculations. Thanks

Algorithm ELISAGoESTOTHEPUB(n): then order Fibonachos else if n is even then ELISAGoESTOTHEPUB(n/2); drink n 2/2 pints of cider; ELISAGoESToTHEPUB(n/2) else for i 1 to 4 do ELISA GoESTOTHEPUB (n 1)/2) drink (n 1)/2 bottles of cider end for drink 1 bottle of cider endif endif For n 0, let C(n) be the number of bottles of cider that Elisa drinks when running algorithm ELISAGoESTOTHEPUB(n). Determine the value of C (n).

Solution

This question is asking you to find the complexity of the program, which will be a function of n.

We find it as :

Let\'s add all of them

C(n) = Log(n) + n^2 + Log(n) + Log(n) + n = 3Log(n) + n^2 + n

C(n) = n^2 + n + Log(n)

This will be the function C(n), but the complexity of this program will be O(n^2) as it\'s the highest order of magnitude in the function.