Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

Question

Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

Does this need to be shown through induction or is it sufficient to say:

Let $d(n) = n$ which is $O(f(n))$.

Therefore $ad(n) = an$ which is trivially $O(f(n))$

Answer 1

No, it is not sufficient to say "let $d(n) = n$ which is $O(f(n))$. Therefore $ad(n) = an$ which is trivially $O(f(n))$". Although that is a reasonable way to to understand the proposition quickly, it is neither sufficient nor necessary. It cannot be considered as a proof. It can easily lead to misunderstanding if communicated.

To show that "if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$", let us apply the relevant definitions.

$$\begin{align*} d(n)\text{ is }O(f(n)) &\Longrightarrow \limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)} <\infty\\ \left(\text{since } \limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)}=a\limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)}\right) &\Longrightarrow\limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)} <\infty\\ &\Longrightarrow\limsup_{n\to\infty}\dfrac{|ad(n)|}{f(n)} <\infty\\ &\Longrightarrow ad(n)\text{ is }O(f(n)).\\ \end{align*}$$

The proof above is rigorous, although it is hardly the way we as humans understand the proposition. Here is another approach.

$$\begin{align*} d(n)\text{ is }O(f(n)) &\Longrightarrow |d(n)|\text{ is bounded above by } cf(n)\text{ when $n$ is large enough for some constant } c\\ &\Longrightarrow |ad(n)|\text{ is bounded above by } acf(n)\text{ when $n$ is large enough for some constant } c\\ (\text{let } c'=ac)\ \ &\Longrightarrow |ad(n)|\text{ is bounded above by } c'f(n)\text{ when $n$ is large enough for some constant } c'\\ &\Longrightarrow ad(n)\text{ is }O(f(n)).\\ \end{align*}$$

The approach above can be considered as a proof among people who are familiar with the stuff. It is probably the way to understand the proposition as well. You can imagine that the graph of $cf(n)$ lies above the graph of $d(n)$, and, hence, the graph of $acf(n)$ lies above the graph of $ad(n)$.

Answer 2

It is not difficult. A meaning of $d(n) = O(f(n))$ is $\lim_{n\to\infty} \frac{d(n)}{f(n)} = c$ which $c$ is constant. Hence, $\lim_{n\to\infty} \frac{a\times d(n)}{f(n)} = a\times c$. Therefore, $a\times d(n) = O(f(n))$.

Answer 3

Write down the definition of Big-O.

From then on it is trivial maths.

The assumptions that you made in your question indicate that you haven't looked at the definition of Big-O, which is why you have to do that first.