# is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?

is it true that if $$f(n)\in O(g(n))$$ then $$f(h(n)) \in O(g(h(n)))$$?

I can't figure out how to prove or disprove this. if it is true, is it true only when the function $$h$$ is invertible?

Suppose $$f(n)=\sqrt{\frac{1}{n}}$$, and $$g(n)=n$$. It's clear that $$f(n)=\mathcal{O}(g(n)).$$ Let $$h(n)=\sqrt{\frac{1}{n}}$$ therefore $$f(h(n))=\sqrt{n}$$ and$$g(n)=\sqrt{\frac{1}{n}}.$$

Obviously $$f(h(n))\neq\mathcal{O}(g(h(n))).$$

Note that if $$\lim_{n\to \infty }h(n)=+\infty$$ then we can conclude that $$f(h(n))=\mathcal{O}(g(h(n))).$$

• But still f(h(n)) is a subset of g(h(n)) from the meaning of the big O notation, otherwise it wouldn't have been possible to say that f(n) is a subset of g(n) in the first place. I think the asker means g(n) is an asymptotic orde complexity of a problem f(n) and wonders if the asymptotic order of a problem with size h(n) would necessarily be O(g(h(n)), right??? My answer if we talking asymptotic order yes; obviously sorting say n/1000 using quicksort is O(n/1000 log n/1000), but it could happen that some problem instance n/1000 takes more than problem instance even n
– ShAr
Aug 30, 2021 at 9:24
• @MohammadRostami, if will accept this as best answer, but it would be nice if you could explain why the limit implies that. Sep 3, 2021 at 6:26

Formally it's easy to bring counterexample: suppose $$f(1)=1$$, $$g(1)=0$$ and then, for other values of argument, $$f, g$$ are any pair of non-zero functions with property $$f(n)\in O(g(n))$$. Now taking $$h(n)=1,\forall n \in \mathbb{N}$$ makes impossible $$f(h(n)) \in O(g(h(n)))$$.

On other hand, for example, if $$h$$ is strictly increasing function, then your claim will be true, because we obtain property for subsequence from sequence.

And about question about invertibility of $$h$$. If we consider counterexample (from comments below) $$f=g=h=1, \forall n \in \mathbb{N}$$, then implication $$f(n)\in O(g(n)) \Rightarrow f(h(n)) \in O(g(h(n)))$$ holds for brought triple, but $$h$$ is not invertible.
• You don’t quite need $h$ strictly increasing, it is enough if $\lim_{n\to\infty}h(n)=\infty$. Aug 30, 2021 at 6:28
• I don’t know whether you are intentionally misreading what I write, but here the exact statement. Let $h\colon\mathbb N\to\mathbb N$ (where $\mathbb N$ includes $0$). Then the following are equivalent: (1) $\lim_{n\to\infty}h(n)=\infty$; (2) for all $f,g\colon\mathbb N\to\mathbb N$, $f(n)=O(g(n))\implies f(h(n))=O(g(h(n)))$. A similar equivalence also holds for functions $\mathbb R_{\ge0}\to\mathbb R_{\ge0}$. Aug 30, 2021 at 14:49
• No, your example does not satisfy (2), because (2) says for all $f,g$, not for some $f,g$. Aug 30, 2021 at 15:24