8
$\begingroup$

I am stuck by analyzing the time complexity of the following algorithm:

def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

The root call will be fun (0, 0, n, n), and n is the size of the problem.

I guess that: The recurrence relation is $ T(n, n) = T(n-1, n) + T(n, n-1)$, which is equivalent to $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$, and so $O(2^m) \iff O(4^n)$.

Is my analysis correct (I know it's not very complete and exact)? If it does have serious flaw, please point it out or show me a correct and complete proof on the time complexity of this algorithm.

$\endgroup$
  • 1
    $\begingroup$ xando, I encourage you to edit the question to explain why the standard techniques don't work: explain why they fail. (Cc: @YuvalFilmus) For instance, do you get a recurrence relation that's hard to solve, and if so, what recurrence do you get? $\endgroup$ – D.W. Oct 4 '15 at 21:35
  • 1
    $\begingroup$ In comments with Polyergic, I've realized that the pseudocode is unclear: it's not clear what you mean for the algorithm to do, when both d>0 and p>0. You don't show what the function returns if we reach the 3rd and 4th if statements. Did you mean to have a return statement after each recursive invocation of fun? (did you mean fun (r, k + 1, d - 1, p) to be return fun (r, k + 1, d - 1, p)?) Or did you mean to have a return statement at the very end of the function body? Please edit your pseudocode to clarify and make sure you show what this returns in all possible cases. $\endgroup$ – D.W. Oct 9 '15 at 23:42
  • $\begingroup$ To say it in another way: suppose d<=p and d>0 and p>0 all hold. What is supposed to happen? Does the algorithm make 2 recursive invocations to the function? Or does it recursively invoke fun(r, k + 1, d - 1, p) and then immediately return, without recursively invoking fun(r, k - 1, d, p - 1)? If I take your pseudocode literally, it appears that it makes 2 recursive invocations and then returns with an undefined return value -- but that seems odd and makes me wonder if there's a typo/bug in the pseudocode. $\endgroup$ – D.W. Oct 9 '15 at 23:45
10
$\begingroup$

The only two arguments relevant to asymptotic analysis are $d$ and $p$. These arguments (virtually) satisfy $d,p \geq 0$ and $d \leq p$ (we need to shuffle the logic in the function slightly to get this). At each point in the execution, you take the current pair $(d,p)$ and then recursively call the function with the pairs $(d-1,p),(d,p-1)$, avoiding pairs which invalidate the constraints stated above.

We can picture the resulting call tree as a path starting at $(0,0)$. Each time you decrease $p$, add a / step. Each time you decrease $d$, add a \ step. The condition $d \leq p$ guarantees that you never go below the X axis. Moreover, you have a "budget" of $n$ of each step. The total number of leaves in this call tree is exactly the Catalan number $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$, and this gives us a lower bound on the running time of the function.

To get an upper bound, note that on the way to each leaf we pass through $2n$ nodes, and this gives an upper bound $2n$ larger than the lower bound, i.e., $\Theta(4^n/\sqrt{n})$.

We have a lower bound of $\Omega(4^n/n^{3/2})$ and an upper bound on $O(4^n/\sqrt{n})$. What are the exact asymptotics? They grow like the total number of paths not crossing the X axis which have at most $n$ steps in each direction. Using Bertrand's ballot theorem we can get an exact expression for this: $$ \sum_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}. $$ It thus remains to estimate this sum asymptotically: $$ \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\ \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\ \sum_{p=0}^n \binom{2p+1}{p+1} - \sum_{p=0}^n \binom{2p+1}{p+2} = \\ \sum_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} = \Theta\left(\sum_{p=0}^n \frac{4^p}{p^{3/2}}\right) = \Theta\left(\frac{4^n}{n^{3/2}}\right). $$

$\endgroup$
  • 1
    $\begingroup$ I really like your geometric approach using these "steps". Is that a common technique? I have not seen it before. $\endgroup$ – Andreas T Oct 5 '15 at 8:24
  • $\begingroup$ @AndreasT I wouldn't call it a common technique, indeed normally it doesn't apply. Here the combinatorial interpretation is pretty evident, and it leads one to this kind of solution. $\endgroup$ – Yuval Filmus Oct 5 '15 at 17:45
0
$\begingroup$

Case by case:

  1. d > p: Constant time
  2. d=0 ∧ p=0: Constant time
  3. d > 0: Note that d ≯ p, so we have 0 < d ≤ p, and fun recurses on d-1 until d ≯ 0; since p > 0, this is Linear in d + (case 4).
  4. p > 0: Note that d ≯ 0, so we have d ≤ 0 ≤ p (with d < p), and fun recurses on p-1 until p ≯ 0; this is Linear in p + (one of case 1, 2, or 5)
  5. d ≤ p < 0: Undefined; I'm assuming this is Constant time

Starting with d = p = n > 0 hits case 3, which is followed by case 4. If n is a whole number, the final case is 2, otherwise the final case is 5. The total time for those cases is d+p+1, or 2n+1.

$\endgroup$
  • $\begingroup$ 2n. I guess you downvoted because I focused on the reasoning? $\endgroup$ – ShadSterling Oct 8 '15 at 3:41
  • 1
    $\begingroup$ Thanks for editing the answer! The puzzle now is that you concluded that the running time is $O(n)$, but Yuval concluded that the running time is exponential in $n$. That's a pretty substantial difference. $\endgroup$ – D.W. Oct 8 '15 at 16:49
  • 1
    $\begingroup$ Hmm, I think I took the pseudocode ifs to be a "do one of these" while @Yuval took them to be "consider each of these in order". The latter is, of course, what ifs (without else) mean in actual code; I'm used to the former in almost any other context than actual code (including in pseudocode, although usage in pseudocode is inconsistent). $\endgroup$ – ShadSterling Oct 9 '15 at 20:28
  • $\begingroup$ I see what you mean. The lack of return statements in the latter half of the code makes this pretty confusing. $\endgroup$ – D.W. Oct 9 '15 at 23:37

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.