algorithmmaxminim

What is the value returned by this function?

My teacher gave us a very hard problem on course of algorithms.

Let's consider the below code in which random(a) is a primitive which returns a random integer value,uniformly distributed in [0;a],and has complexity Theta(1).

  int test(int n)
{
  if(n<=2) return n;
  int i = random(n-2);
  return test(i) + test(n-2-i);
}

  1. What may return function for n = 9;

  2. What is the minimum value for the expression test(2016)?

  3. What is the maximum value for the expression test(2016)?

I tried to generalize the expression for an generic step k but I get stuck in the probabilistic things and I don't know how to express them. It's not a homework, it's just something to think about.

Solution

  • Let's try to calculate test(i) for i:3..9 to know what it may return for 9
    We have test(n) = test(i) + test(j) with i+j = n-2, i <= n-2 and j <= n-2
    test(3)= test(1) + test(0) = 1
    test(4)= test(2) + test(0) || test(1)+ test(1) = 2
    test(5)= test(3) + test(0) || test(2) + test(1) = 1 || 3 (here start the problems)
    test(6) = test(4)+ test(0) || test(3)+ test(1) || test(2)+ test(2) = 2 || 4
    test(7) = test(5)+ test(0) || test(4)+ test(1) || test(3)+ test(2) = 1 || 3
    test(8) = test(6)+ test(0) || test(5)+ test(1) || test(4)+ test(2) || test(3)+ test(3)= 2 || 4
    test(9) = test(7)+ test(0) || test(6)+ test(1) || test(5)+ test(2) || test(4)+ test(3)= 1 || 3 || 5
    So test(n) may return even number that are lower than n if n%2 =0, and an even number that are lower than n in the other case (which is cool)
    As for minimum test(2016) if the random always return 0 you will have test(2016)= test(2014)....=test(2) =2
    For max test(2016) it is 1008, if the random always return (n-2)/2
    I made the edit test(2016) = 1008 in fact
    test(4n) may return {2,4,...,2n}
    test(4n+1) may return {1,3,...,2n+1}
    test(4n+2) may return {2,4,...,2n+2}
    test(4n+3) may return {1,3,...,2n+1}
    I think that this can be verified by induction, it is true for n =1
    test(4n+4) = test(2) + test(4n) since test(4n) may return = 2n we have test(4n+4) may return 2n + test(2) = 2n +2
    since test(4n+4) may return test(4n+2) and also test(4n) => test(4n+4) may return all the value returned by test(4n) => it can return {2,4,... 2n+2}
    It is abvious that test(4n+4) can't return an aneven number it is the sum of tow test(i) and test(j) and since i+j = 4n+4, i and j are both even or both an even and with induction's assumption the result is an even number.
    Last step is to prove that test(4n+4) can't be bigger than 2n +2:
    test(4n+4) = test(i) + test(j) with i+j = 4n +2, again with induction's assumption max(test(i)=< (i/2)+1 and max(test(j)) <= (j/2)+1
    so test(4n+4) <= 2n + 3 and since it is an even number test(4n+4) <= 2n + 2.