1
$\begingroup$

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?

$\endgroup$

2 Answers 2

0
$\begingroup$

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[4]{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))).$$

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – ShAr
    Aug 30, 2021 at 9:24
  • $\begingroup$ @MohammadRostami, if will accept this as best answer, but it would be nice if you could explain why the limit implies that. $\endgroup$
    – violet
    Sep 3, 2021 at 6:26
1
$\begingroup$

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.

Addition.

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.

$\endgroup$
13
  • 1
    $\begingroup$ You don’t quite need $h$ strictly increasing, it is enough if $\lim_{n\to\infty}h(n)=\infty$. $\endgroup$ Aug 30, 2021 at 6:28
  • $\begingroup$ It's one possible example, @Emil Jeřábek, mathematically they are independent and, sure, can be named more other sufficient conditions. $\endgroup$
    – zkutch
    Aug 30, 2021 at 6:59
  • $\begingroup$ No, actually, what I wrote is a sufficient and necessary condition. $\endgroup$ Aug 30, 2021 at 8:01
  • 1
    $\begingroup$ 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}$. $\endgroup$ Aug 30, 2021 at 14:49
  • 1
    $\begingroup$ No, your example does not satisfy (2), because (2) says for all $f,g$, not for some $f,g$. $\endgroup$ Aug 30, 2021 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.