Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

Question

I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG. (Randomly Generated Number)

Let's begin with the pseudo-code, and then I will go into what I have thought about so far related to this one.

Func1(A, i, j)
/* A is an array of at least j integers */

1 if (i ≥ j) then return (0);
2 n ← j − i + 1 ; /* n = number of elements from i to j */
3 k ← Random(n);
4 s ← 0; //Takes time of Arbitrary C

5 for r ← i to j do
6 A[r] ← A[r] − A[i] − A[j]; //Arbitrary C
7 s ← s + A[r]; //Arbitrary C
8 end

9 s ← s + Func1(A, i, i+k-1); //Recursive Call 1
10 s ← s + Func1(A, i+k, j); //Recursive Call 2
11 return (s);

Okay, now let's get into the math I have tried so far. I'll try not to be too pedantic here as it is just a rough, estimated analysis of expected run time.

First, let's consider the worst case. Note that the K = Random(n) must be at least 1, and at most n. Therefore, the worst case is the K = 1 is picked. This causes the total running time to be equal to T(n) = cn + T(1) + T(n-1). Which means that overall it takes somewhere around cn^2 time total (you can use Wolfram to solve recurrence relations if you are stuck or rusty on recurrence relations, although this one is a fairly simple one).

Now, here is where I get somewhat confused. For the expected running time, we have to base our assumption off of the probability of the random number K. Therefore, we have to sum all the possible running times for different values of k, plus their individual probability. By lemma/hopefully intuitive logic: the probability of any one Randomly Generated k, with k between 1 to n, is equal 1/n.

Therefore, (in my opinion/analysis) the expected run time is:

ET(n) = cn + (1/n)*Summation(from k=1 to n-1) of (ET(k-1) + ET(n-k))

Let me explain a bit. The cn is simply for the loop which runs i to j. This is estimated by cn. The summation represents all of the possible values for k. The (1/n) multiplied by this summation is there because the probability of any one k is (1/n). The terms inside the summation represent the running times of the recursive calls of Func1. The first term on the left takes ET(k-1) because this recursive call is going to do a loop from i to k-1 (which is roughly ck), and then possibly call Func1 again. The second is a representation of the second recursive call, which would loop from i+k to j, which is also represented by n-k.

Upon expansion of the summation, we see that the overall function ET(n) is of the order n^2. However, as a test case, plugging in k=(n/2) gives a total running time for Func 1 of roughly nlog(n). This is why I am confused. How can this be, if the estimated running time is of the order n^2? Am I considering a "good" case by plugging in n/2 for k? Or am I thinking about k in the wrong sense in some way?

Answer 1

Expected time complexity is ET(n) = O(nlogn) . Following is math proof derived by myself please tell if any error :-

ET(n) = P(k=1)*(ET(1)+ET(n-1)) + P(k=2)*(ET(2)+ET(n-2)).......P(k=n-1)*(ET(n-1)+ET(1)) + c*n

As the RNG is uniformly random  P(k=x) = 1/n for all x

hence ET(n) = 1/n*(ET(1)*2+ET(2)*2....ET(n-1)*2) + c*n

ET(n) = 2/n*sum(ET(i)) + c*n i in (1,n-1)

ET(n-1) = 2/(n-1)*sum(ET(i)) + c*(n-1) i in (1,n-2)

sum(ET(i)) i in (1,n-2) = (ET(n-1)-c*(n-1))*(n-1)/2

ET(n) = 2/n*(sum(ET(i)) in (1,n-2) + ET(n-1)) + c*n

ET(n) = 2/n*((ET(n-1)-c*(n-1))*(n-1)/2+ET(n-1)) + c*n

ET(n) = 2/n*((n+1)/2*ET(n-1) - c*(n-1)*(n-1)/2) + c*n

ET(n) = (n+1)/n*ET(n-1) +  c*n - c*(n-1)*(n-1)/n

ET(n) = (n+1)/n*ET(n-1) + c

solving recurrence

ET(n) = (n+1)ET(1) + c + (n+1)/n*c + (n+1)/(n-1)*c + (n+1)/(n-2)*c.....


ET(n) = (n+1) + c + (n+1)*sum(1/i) i in (1,n)


sum(1/i) i in (1,n) = O(logn)


ET(n) = (n+1) + c + (n+1)*logn


ET(n) = O(nlogn)