3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you familiar with the run-time analysis of quicksort? $\endgroup$ – Joe Feb 12 '14 at 6:44
  • $\begingroup$ Double check your expansion of the summation. $\endgroup$ – Joe Feb 12 '14 at 8:08
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Feb 12 '14 at 9:05
  • $\begingroup$ THe analysis of quicksort does not apply directly to this problem although it is similar. $\endgroup$ – Musicode Feb 12 '14 at 16:00
1
$\begingroup$

How does the recursive formula for $E[T(n)]$ compare between this algorithm and randomized quicksort? They are very similar, which might lead one to believe that the running time of your algorithm is $\Theta(n \log n)$. In fact, the recursive formula for the run-time is so similar to the one for quicksort, that you could use that fact in itself as a proof. There are more elegant ways to prove it, but you can also prove it by induction.

$$ T(n) \leq bn + \frac{1}{n}\sum_{k = 1}^n T(k) + T(n-k) $$

$$ = bn + \frac{2}{n}\sum_{k = 1}^{n-1} T(k). $$

Suppose (induction hypothesis) that $T(i) \leq ci \ln i$ for $i \le n - 1$.

Then use the standard trick of bounding a sum by an integral: $\sum_{i=1}^{n-1}f(i) \leq \int_1^n f(x) dx$.

The rest of the proof works like a standard proof by induction with just a little algebra.

Here's a nice source for this and other proofs of the running time of quicksort, and the techniques apply to this problem as well.

Notes on randomized quicksort analysis

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.