Counterexample for false O notation statement

76 Views Asked by At

Stumbled upon some O notation counterexamples, but can't seem to figure out which one would disprove this statement:

For any positive constant $c$, $f(cn)\in O(f(n))$.

Any help would be appreciated!

2

There are 2 best solutions below

0
On BEST ANSWER

Hint: $f(cn) \in O(f(n))$ is equivalent to $\left|\frac{f(cn)}{f(n)}\right|$ being bounded.

Hint: try an exponential function $f$.

0
On

Let $f(n)=2^n$. Then $f(cn)=2^{cn}$ so $\frac {f(cn)}{f(n)}$ is not bounded.