If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?

cs.stackexchange https://cs.stackexchange.com/questions/130356

  •  29-09-2020
  •  | 
  •  

Suppose the following is true for some f(n) and g(n): $f(n) = \Theta(g(n))$

Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?

I know that for the above to be true, there must exist positive constants $c_1$, $c_2$, $n_0$ such that for all $n \geq n_0, $ $c_1(g(n)) \leq f(n) \leq c_2(g(n))$. Thus if $f(n) = \Theta(g(n))$, then can I assume:

$\frac{1}{k}c_1(g(n)) \leq f(n/k) \leq \frac{1}{k}c_2(g(n))$ to satisfy big Theta?

My apologies if this is totally obvious or if I'm completely on the wrong track, my math background isn't the strongest. Are there any relevant properties that might describe this relationship?

有帮助吗?

解决方案

Take $f(n) = n^4$. For this function, if you double the argument, the result is multiplied by 16, that is by a constant factor. Now take $g(n) = 2^n$. For this function, if you double the argument, the result is squared, and since $2^n$ can grow arbitrarily large, there is no limit to the growth factor achieved by squaring g(n).

That’s the difference. If the growth from doubling the argument has an upper limit then $\Theta$ stays the some, otherwise it doesn’t.

其他提示

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.

For given $f(n)$, well defined, for $\forall n\in \mathbb{N}$, the function $f(n/x)$ can be even undefined: for example $f(n)=\frac{1}{n-\frac{1}{2}}$ and $x=2$.

More sophisticated example is $$ f(n)=\begin{cases} 2^k, & n=2k+1 \\ k, & n=2k \end{cases} $$ Obviously $f(2n) \in \Theta(n)$, but $f(n)\notin \Theta(n)$.

Case, where your sentence is true is, for example, homogeneous function with homogeneous degree $k=1$ i.e. when $g(Cx)=Cg(x)$ and we consider homogeneous functions subset from $\Theta(g)$.

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top