Prove or provide a counterexample: For every positive constant c, and every function f from nonnegative ints into nonnegative reals, $$f(cn) \in \theta (f(n))$$.
At first, I thought this was obvious, then me and a friend ended up with radically different answers. My first thought was that a constant times a number would do nothing to the theta of the function, but according to him, it would make $f(cn) \in \theta (f(n^2))$ , but im not buying that. Then theres my sister ( 3 years younger) who says were both idoits! Please help!
HINT: In your list of standard ‘sizes’ you probably have $\Theta(1)$, $\Theta(\lg n)$, $\Theta(n^k)$ for different values of $k$, $\Theta(2^n)$, $\Theta(n!)$, $\Theta(n^n)$, and maybe a few more. Experiment with these functions, especially some of the faster-growing functions, examining how the ratio $\frac{f(cn)}{f(n)}$ behaves as $n\to\infty$. The slower-growing functions and the exponential are especially easy to check.