Big O Notation Proofs Without Concrete Functions

Question

I've looked around for this and I can't find anything close to what I'm looking for.

Usually when I saw Big O notation in my classes it was something like:

$n^2 + 2n + 1 = O(n^2)$

However, the question I'm being issued now is:

If $f(n)$ is $O(g(n))$, prove or disprove this statement:

$f(n^2)$ is $O(g(n^2))$

Now, I don't know where to go from here beyond:

$f(n^2) = c * g(n^2)$

It's driving me absolutely nuts.

$f(n)$ is $O(g(n))$ means there are constants $C$ and $k$ such that $f(n) \le C\cdot g(n)$ when $n\ge k$. What happens when you replace $n$ with $m^2$? — Christopher Carl Heckman, Oct 02 '15 at 07:22
You get m^4? I just don't know how to handle stuff with f(n) and g(n) instead of equations like n^2 + 2n. — NotAStudentForReal, Oct 02 '15 at 07:24
What do you get when you replace $n$ with $m^2$ in $f(n) \le C \cdot g(n)$? — Christopher Carl Heckman, Oct 04 '15 at 06:08

score 0 · Answer 1 · answered Oct 02 '15 at 08:00

0

$f(n)=O(g(n))$ means the ratio $\dfrac{\lvert f(n)\rvert}{\lvert g(n}\rvert$ is bounded from above for all $n$ large enough such that $g(n)\ne 0$.

The same is clearly true for any function $u(n)$ such that $\lim\limits_{n\to\infty}=+\infty$, since, if the above bound is valid for any $n\ge N_0$, there exists an interger $N_1$ such that $u(n)\ge N_0$ for all $n\ge N_1$.

answered Oct 02 '15 at 08:00

Bernard

175,478

That's part of the definition of Big O, right? I just don't know how to apply that to the problem. – NotAStudentForReal Oct 02 '15 at 08:22

Big O Notation Proofs Without Concrete Functions

1 Answers1