Analysis of Algorithm question procedure MYSTERY int n int a

Analysis of Algorithm question

procedure MYSTERY (int n, int a) if (n ==0) then return 0 end if int tmpl = MYSTERY(n/2, a)//assume n/2 rounds down. int tmp2 = 0 for int i = 1 to n/2 do tmp2 + = a end for if (n%2 ==1) then return tmp1 + tmp2 + a else return tmp1 + tmp2 end if end procedure Consider the previous recursive algorithm MYSTERY that takes as input integers n and a What does the mystery function compute? Set up a runtime recurrence for the mystery method above. Do not forget the base case. Is this mystery function a divide-and-conquer algorithm? Briefly justify your answer.

Solution

In general, this problem requires f(n) = some time period be solve for a value n.

This can be done for all case expect n lg n and n!, which will be evaluated numerically

F(n) = lg n microsec = 1 sec => 2lg n = 21E6 => n = 21E6 1 second 1 minute 1 hour 1 day 1 month 1 year 1 century lg n 21E6 26E7 23.6E9 28.64E10 22.59E12 23.15E13 23.15E15 n0.5 1.00E12 3.60E15 1.30E19 7.46E21 6.72E24 9.95E26 9.95E30 n 1E6 6E7 3.6E9 8.64E10 2.59E12 3.15E13 3.15E15 n lg n 62746 2.8E6 1.33E8 2.75E9 7.18E10 7.97E11 6.86E13 n 2 1.00E03 7.75E03 6.00E04 2.94E05 1.61E06 5.62E06 5.62E07 n3 100 391 1532 4420 13736 31593 146645 2n 19 25 31 36 41 44 51 n! 9 10 12 13 15 16 17

In solving for problems like n! and n lg n, numerically solving in Excel is an acceptable approach. For example, let cell A1 equal n and cell A2 equal “=FACT(A1)” Next, we recognize 1 second equals 1x106 microseconds. So, increase cell A1 until cell A2 equals 1x10