2
$\begingroup$

A recursive algorithm has the following computation tree. The label on the node indicates the number of outgoing edges. This algorithm takes an input of length $n$ and at each processing, it results in $n - 1$ recursive calls. For each these calls/nodes, the size of the input decreases by $1$ from left to right. This pattern repeats.

enter image description here

I'm trying to figure out how to come up with a complexity analysis for this. It feels like there's some mathematical pattern/sequence here but I'm not able to figure it out.

$\endgroup$

1 Answer 1

1
$\begingroup$

Vertices in your tree correspond to decreasing sequences starting at $n$. We can identify each such subsequence with a subset of $\{0,\ldots,n-1\}$, and consequently, your tree contains $2^n$ vertices. Consequently, assuming the processing per node is $O(1)$, your algorithm runs in time $\Theta(2^n)$.

The same method also allows us to count directly the number of vertices labelled $m$: there are $2^{n-m-1}$ of these for $m \in \{0,\ldots,n-1\}$, and one labelled $n$ (the root).


Here is another way to solve this, using a recurrence. Let $T(n)$ be the size of the tree when the root is labelled $n$. Then $T(0) = 1$ and $$ T(n + 1) = 1 + \sum_{m=0}^n T(m). $$ This formula actually works also for $n = -1$. In order to solve this recurrence, observe that $$ T(n+1) = 1 + \sum_{m=0}^{n-1} T(m) + T(n) = 2T(n), $$ and so $T(n) = 2^n T(0) = 2^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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