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

Computer Science Asked by Rolodecks on December 8, 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.

Correct answer by gnasher729 on December 8, 2020

For given $$f(n)$$, well defined, for $$forall nin 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)$$.

Answered by zkutch on December 8, 2020

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.

Answered by Watercrystal on December 8, 2020

## Related Questions

### Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

1  Asked on November 28, 2021 by user2207686

### Number of words of length n for special language

0  Asked on November 28, 2021

### Intuition for Church-Turing thesis for Turing machines

2  Asked on November 28, 2021

### Global-input-local-output p-time algorithms

0  Asked on November 25, 2021

### Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

2  Asked on November 25, 2021 by hish

### Is $EVEN-SAT$ $NP$-hard?

2  Asked on November 23, 2021 by zur-luria

### Proof of the undecidability of compiler code optimization

5  Asked on November 23, 2021 by stephen-mwangi

### Counting circuits with constraints

1  Asked on November 23, 2021 by judy-l

### Uncurrying and Polymorphism

3  Asked on November 21, 2021

### Algorithm suggestion to order data with specific condition

0  Asked on November 21, 2021 by user3862410

### If $A$ is context-free then $A^*$ is regular

1  Asked on November 21, 2021

### Which is the best approach to solve Turing machines exercises?

2  Asked on November 17, 2021 by ocram

### What is the reason for writing parallel programs?

1  Asked on November 17, 2021 by user123521

### Are all Recursively Enumerable languages which are not Recursive also Undecidable?

1  Asked on November 17, 2021 by dshri

### Is English Turing-complete?

3  Asked on November 15, 2021

### If factor isn’t found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

0  Asked on November 13, 2021 by northerner

### Can map-reduce speed up the count-min-sketch algorithm?

1  Asked on November 11, 2021 by pragya

### Maximization problem on finite collection of finite sets

1  Asked on November 11, 2021 by yuezato

### Do there exist fast multiplication algorithms for two integers with one of them being static?

1  Asked on November 8, 2021 by john-flemin

### Convert the given NFA to DFA

2  Asked on November 5, 2021 by vinay-varahabhotla