The question is:
T(n) = aT(n/b) + n. Some of them give a runtime that is O(n), and some don’t. Find the relationship between a and b that yields T(n) = O(n), and prove that this is sufficient.
The solution mentioned was this:
[NOTE: when they mention integral they are talking integral inside of theta in Akra Bazi theorem.]
From analyzing the integral we can see that any case where p < 1 will give a linear solution, so having the condition a < b is sufficient.
My answer was this:
The relationship should be such that a * b < 1.
Justification: if a*b is < 1 then that means denominator of b is greater than a and therefore p will be less than 1. Then if p is less than 1 solving integral inside theta of Akra Bazi and doing algebraic simplification always gives growth such that we get O(n).
is my answer correct?
We have the recurrence relation:
$$ T(n) = aT\left(\frac{n}{b} \right) + n = aT\left( dn \right) + n $$
with $d = \frac{1}{b}$. Applying Akra-Bazzi we get:
$$ T(n) = \Theta \left( n^p + n^p \int_1^n \frac{x}{x^{p + 1}} dx\right) = \Theta \left( \frac{-p}{-p + 1} n^p + \frac{n}{-p + 1} \right) $$
From which we conclude that $T(n) = \Theta(n)$ if $p < 1$. Now $p$ is computed from $ad^p = 1$ or $b^p = a$ so we get $p = \frac{\ln a}{\ln b}$ which means if $p < 1$ then $1 > \frac{\ln a}{\ln b}$ or $ a < b$. And so we conclude $T(n) = \Theta(n)$ if $a < b$ as given by the solution you mentioned.