0

Question: If $f(n) = af(n/a) + c \log n$, how does $f(n)$ grow?

This is an attempt to correct my answer here: https://math.stackexchange.com/questions/1188652/time-complexity-of-recurrence-fn-3f-fracn3ologn/1188673#1188673

It turns out my answer there and my original answer here were wrong. My thanks to Henning Makholm for showing where my error was.

My solution now agrees with others:

$f(n) =O(n) $ where the constant implies by the $\omega$ depends on $a$ and $c$.

Proof:

$\begin{array}\\ f(n) &=af(n/a)+c\log n\\ &=a(af(n/a^2)+c\log (n/a)))+c\log n\\ &=a^2f(n/a^2)+(ac+c)\log n-ac \log a\\ &=a^2f(n/a^2)+c(a+1)\log n-ac \log a\\ &=a^2(af(n/a^3)+c\log (n/a^2))+c(a+1)\log n-ac \log a\\ &=a^3f(n/a^3)+a^2c\log n-2a^2c\log a+c(a+1)\log n-ac \log a\\ &=a^3f(n/a^3)+c(a^2+a+1)\log n-ac(1+2a) \log a\\ &=a^4f(n/a^4)+c(a^3+a^2+a+1)\log n-ac(1+2a+3a^2) \log a\\ &...\\ &=a^mf(n/a^m)+cs(m)\log n-act(m)\\ \end{array} $

$\sum_{i=1}^{m-1} i a^{i-1} = ((m-1) a^{m+1}-m a^m+a)/((a-1)^2 a) $

where $s(m) =1+a+a^2+...+a^{m-1} =(a^m-1)/(a-1) $ and

(here's where my mistake is: I had the wrong formula for $t(m)$)

$\begin{array}\\ t(m) &=1+2a+3a^2+...+(m-1)a^{m-2}\\ &=((m-1) a^{m+1}-m a^m+a)/((a-1)^2 a)\\ &=(ma^m(a-1)-a^{m+1}+a)/((a-1)^2 a)\\ \end{array} $.

Therefore

$\begin{array}\\ cs(m)\log n-act(m) &=c\log n(a^m-1)/(a-1)-ac(ma^m(a-1)-a^{m+1}+a)/((a-1)^2 a)\\ &=\dfrac{ca(a-1)\log n(a^m-1)-ac(ma^m(a-1)-a^{m+1}+a)}{((a-1)^2 a)}\\ &=ac\dfrac{(a-1)\log n(a^m-1)-(ma^m(a-1)-a^{m+1}+a)}{((a-1)^2 a)}\\ \end{array} $

and the numerator is

$(a-1)\log n(a^m-1)-(ma^m(a-1)-a^{m+1}+a) =(a-1)a^m(\log n - m)-(a-1)\log n+a(a^m-1) $

Since $1 \le n/a^m < a$, $0 < \log n - m \log a < \log a$ or $\log n - m \log a =O(1) $, so this term is $O(a^m) =O(n)$.

If $n = a^m$, $m = \log n$ so the numerator is $-(a-1)\log n+a(n-1) = \Omega(n) $ and $f(n) = \Omega(n)$.

So I was wrong.

Community
  • 1
marty cohen
  • 107,799

1 Answers1

1

In the case where $n$ is a power of $a$, say $n=a^k$, I get

$$ \begin{align} f(n) &= nf(1) + \frac n{a}c\log(a) + \frac n{a^2}c\log(a^2) + \frac n{a^3}c\log(a^3) + \cdots + \frac{n}{a^k}c\log(a^k) \\ &= nf(1)+ cn\log(a)\bigl( \frac 1{a} + \frac2{a^2} + \frac 3{a^3} + \cdots + \frac k{a^k} \bigr) \\ &< nf(1) + cn\log(a)\sum_{j=1}^\infty j(1/a)^j \\ &= nf(1) + cn\log(a)\frac{a}{(a-1)^2} \end{align} $$

So for these $n$ we have $$ nf(1) \le f(n) \le n\left(f(1)+c\log(a)\frac{a}{(a-1)^2}\right) $$

For arguments that are not powers of $a$, $f$ is certainly increasing, so what $f$ does between the powers of $a$ can at most vary it by a factor of $a$ from the linear growth above. Therefore, $$ f(n) = \Theta(n) $$

hmakholm left over Monica
  • 286,031