Question

11. Show that if positive functions f(x) and g(x) grow at the same rate as x→∞, then f=O(g) and g=O(f).

Accepted Answer

Recall the definition of "growing at the same rate" as $$x 	o \infty$$: two positive functions $$f(x)$$ and $$g(x)$$ grow at the same rate if the limit $$\lim_{x 	o \infty} \frac{f(x)}{g(x)}$$ exists and is a positive finite constant, say $$L \u003e 0. $$From the limit $$\lim_{x 	o \infty} \frac{f(x)}{g(x)} = L$$, we can write that for sufficiently large $$x$$, the ratio $$\frac{f(x)}{g(x)} is $$close to $$L. $$This implies there exist constants $$c_1$$, $$c_2$$ \u003e 0$$ and x_0$ such that for all x$$ \u003e $$x_0$$, $$c_1$$ \leq \frac{f(x)}{g(x)} \leq $$c_2. $$Rearranging the inequalities, we get $$c_1 g(x$$) \leq f(x) \leq $$c_2 g(x$$)$$ for all x$$ \u003e $$x_0. $$This shows that $$f(x) is $$bounded above and below by constant multiples of $$g(x)$$ for large $$x. By $$the definition of Big-O notation, $$f = O(g)$$ means there exist constants $$M \u003e 0$$ and $$x_1$$ such that $$|f(x)| \leq M |g(x)|$$ for all $$x \u003e x_1$. From the inequality above, we can choose M$$ = $$c_2$$ and $$x_1$$ = $$x_0 to $$conclude $$f = O(g). $$Similarly, since $$c_1 g(x$$) \leq f(x)$$, we can rewrite this as g(x$$) \leq \frac{1}{$$c_1$$} f(x)$$ for x$$ \u003e $$x_0. $$This shows $$g = O(f) by $$choosing appropriate constants, completing the proof that if $$f$$ and $$g$$ grow at the same rate, then $$f = O(g)$$ and $$g = O(f).$$

11. Show that if positive functions f(x) and g(x) grow at the same rate as x→∞, then f=O(g) and g=O(f).

Verified video answer for a similar problem:

Key Concepts

Big-O Notation

Growth Rate of Functions

Limits and Asymptotic Equivalence