finding the asymptotic growth bound for the following floor/ceiling recurrence

Question

Suppose we have $$ T(n)=0 \quad,\quad n\leq3 $$ $$ T(n)= T(\lceil n/3\rceil)+T(\lfloor n/4\rfloor)+7n\quad,\quad n\geq4 $$

how does one show that the upper and lower bounds are matching? (i.e. find $\Theta(...) $)

I tried evaluating the first few values, we find that $T(n)=7\cdot n$ for $4\leq n\leq 9$.

For $10\leq n \leq 12$, $T(\lceil n/3\rceil)=4$, so $$T(n)=T(4)+7\cdot n$$ $$T(n)=28+7\cdot n $$

so hand wavily, to find a lower bound, I'll argue that $T(n)$ essentially grows linearity given the $7n$ term, and past $n=10$, other terms begin contributing as well, but those are also linear, so we have

$$O(T(n))=O(n)+O(n)+O(n)$$ $$=O(n)$$

to upper bound the function, we can claim that

$$\begin{align*}T(\lceil n/3\rceil) \leq&\ 7n\\ T(\lfloor n/4\rfloor)\leq&\ 7n \\ \implies T(n) \leq&\ 7n+7n+7n \\ \implies \Omega(T(n)) =&\ \Omega(n) \end{align*}$$

therefore $O(T(n))=\Omega(T(n))$ and therefore $\Theta(T(n))=\Theta(n)$ as well?

EDIT:

I guess to lower bound, could I just say $T(n) \geq 7n$, thus it has a $O(n)$ lower bound?

Answer 1

I would recommend using the tree method. At level $i$ of the recursion tree, what is the non-recursive work at each node? What is the total non-recursive work at level $i$?

• At level $i = 0$, we have work $7n$.
• At level $i = 1$, we have work $7[n/3 + n/4]$.
• At level $i = 2$, we have work $7[n/3^{2} + n/(3 * 4) + n/(3 * 4) + n/4^{2}]$.
• What is the work at level $i = 3$?

Note that since you have a binary tree structure for the recurrence, the binomial theorem may be helpful.

Now once you have determined the amount of work at each level, add up:

$$\sum_{i=0}^{\# \text{levels}-1} \text{work at level } i.$$

Does this help you get started?