patternMinor
Does $f(n) = O(g(n))$ imply $f(h(n)) = O(g(h(n)))$?
Viewed 0 times
implydoesstackoverflow
Problem
Can we prove the following, or find a counterexample?
$$f(n) = O(g(n)) \Longrightarrow f(h(n)) = O(g(h(n)))$$
I should figure out whether $\log(n^{\log n}) = O(a^{\log n})$, and this will be facilitated if the above holds.
$$f(n) = O(g(n)) \Longrightarrow f(h(n)) = O(g(h(n)))$$
I should figure out whether $\log(n^{\log n}) = O(a^{\log n})$, and this will be facilitated if the above holds.
Solution
Let's assume for simplicity that $f(n),g(n)$ both take positive integer values. Then $f(n) = O(g(n))$ iff there exists $C>0$ such that $f(n) \leq Cg(n)$ for all $n$. This implies that for any $h\colon \mathbb{N} \to \mathbb{N}$, $f(h(n)) \leq Cg(h(n))$ holds for all $n$, and so $f(h(n)) = O(g(h(n)))$.
In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C>0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim_{n\to\infty} h(n) = \infty$. In particular, there exists $M>0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.
In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C>0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim_{n\to\infty} h(n) = \infty$. In particular, there exists $M>0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.
Context
StackExchange Computer Science Q#131514, answer score: 2
Revisions (0)
No revisions yet.