Skip to main content
added 750 characters in body
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.


If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take $$ f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)} $$ Then $$ f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}). $$ On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.


If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take $$ f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)} $$ Then $$ f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}). $$ On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.

Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.