-2
$\begingroup$

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(x) &= \begin{cases} f(x-1) + g(x/2) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \end{align*} $$

$\endgroup$
0
$\begingroup$

By induction, $f(x)$ can be expressed non-recursively as a sum over $g$. That can be substituted into the definition of $g$ to get a single recursion, which can be compared to a well-known standard recurrence to show a lower bound. Finally, the comparison is close enough to hint that the upper bound must be similar to the lower bound, so you should be able to guess an upper bound and prove it.

| cite | improve this answer | |
$\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.