Given: $$f(1) = 1 \\ f(n) = 4f(n-1) + f(n/3) + f(n/8)$$ (if $n<1$ then it is still 1) And I need to find $\Theta(f(n))$, can I do this?

$$ \Theta( f(n)) = \Theta(4f(n-1)) + \Theta(f/3)) + \Theta(f(n/8))$$

Then solve each term and get that it is $\Theta(4^n)$ ?

Or it is not possible as we basically have this:

$$ f(n) = 4 ( 4f(n-2) + f((n-1)/3) + f((n-1)/8)) + f(n/3) + f(n/8) $$ etc... and by the end we have:

$$ \sum_{m=0}^{n} 4^{m} ( f((n-m)/3) + f((n-m)/8)) $$

But this seems so incorrect because then each term in the sum calls the functions again with its value, thus making another sum and another sum..
this is really crazy and I cannot comprehend it in my head, I would be thankful for any kind of hint/answer. Thanks!

  • $\begingroup$ Try proving by induction that $f(n)\leq c(4^n-2^n)$ for some large enough constant $c$. $\endgroup$
    – Tassle
    Commented Feb 16, 2021 at 23:17
  • $\begingroup$ @Tassle What about the lower bound? is it also bigger than $c_1 (4^n - 2^n)$ how did you get to $2^n$ ? Thanks! $\endgroup$
    – CSch of x
    Commented Feb 16, 2021 at 23:40
  • $\begingroup$ The lower bound is easier, you can simply use $f(n)\geq 4f(n-1)$ to show that $f(n)\in \Omega(4^n)$. Together with the upper bound this gives $f(n)\in \Theta(4^n)$. As for the $2^n$, it is just a number I picked which makes the inductive proof work out, but you could choose something else. Try showing $f(n) \leq c4^n$ directly by induction, you'll likely run into some trouble. Sometimes, trying to show something stronger actually makes the proof easier, which is the case here. $\endgroup$
    – Tassle
    Commented Feb 17, 2021 at 1:06
  • $\begingroup$ @Tassle thanks. I have another question, will the akrabazzi method work here? Cant we use the iteration method alongside with akra bazzi and say that it is $4^n$ plus <akrabazzi answer> which would be smaller? And a little question; does the akra bazzi needs finite amount of $af(n/b)$ or it can be a sum that depends of your "$n$" such as $ \sum_{l=1}^{n} af(n/b)$ <-- can you use akrabazzi if there is a sum like this? $\endgroup$
    – CSch of x
    Commented Feb 17, 2021 at 11:16
  • $\begingroup$ You can't decompose into $4^n$ + <other method> because the other $f(n)$'s which appear are not independent, the $4^n$ is also part of their recursive definition. Maybe there is a way to make the Akra-Bazzi method work by some change of domain but I don't see it. As for the number of terms in the recursive definition, they do need to be fixed in the Akra-Bazzi method, but I'm not positive it couldn't be generalized for case like the one you mention. I don't know :) $\endgroup$
    – Tassle
    Commented Feb 17, 2021 at 12:14


Your Answer

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

Browse other questions tagged or ask your own question.