1
$\begingroup$

In CLRS, exercise 4.4-5 the following question is asked:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$

In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$ and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.

Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$ and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?

$\endgroup$
0
$\begingroup$

For each specific level $i$, it is true that the cost is $(3/2)^i n - O(1)$. However it would be misleading to state this in general. Suppose for example that the cost at level $i$ were $(3/2)^i n + 2^{2^i}$, and that there were $\log n$ levels. The dominant factor in the total cost would be the "constant" term.

However, in your case, you can say that the cost at level $i$ is at most $(3/2)^i$, which gives you the required upper bound.

$\endgroup$
2
  • $\begingroup$ In that case, how would you handle cases where such constant terms are added instead of subtracted? $\endgroup$
    – Cirrus86
    Feb 12 at 10:56
  • $\begingroup$ You need to estimate them as a function of $i$. No way around it. $\endgroup$ Feb 12 at 11:01
0
$\begingroup$

Regarding the recurrence itself. First, for concreteness, let us define $T(0) = 0$ and for $n > 0$, $$ T(n) = T(n-1) + T(\lfloor n/2 \rfloor) + n. $$ Let $S(n) = T(n) + 2n$. Then $$ S(n) = T(n) + 2n = T(n-1) + T(\lfloor n/2 \rfloor) + 3n = S(n-1) + S(\lfloor n/2 \rfloor) + n+1 - 2\lfloor n/2 \rfloor,$$ and $S(0) = 0$. Note that $n+1-2\lfloor n/2 \rfloor \in \{1,2\}$. Therefore if we define a $R(0) = 0$ and $$ R(n) = R(n-1) + R(\lfloor n/2 \rfloor) + 1 $$ then $S(n) = \Theta(R(n))$ and so $T(n) = \Theta(R(n)) - 2n$.

Now let $U(n) = R(n) + 1$. Then $U(0) = 1$ and $$U(n) = U(n-1) + U(\lfloor n/2 \rfloor).$$ Thus $U(n)$ is the number of ways to reach $0$ using two operations: subtract $1$ and right shift by $1$. Also, $R(n) = U(n) - 1$, and so $T(n) = \Theta(U(n)) - 2n$, which is going to equal $\Theta(U(n))$.

The sequence $U$ is also known as A000123, where other interpretations are given. The asymptotics of the sequence are known to be $n^{\Theta(\log n)}$. More accurate answers can be found on the OEIS references.

$\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.