Can someone explain me how it's possible to have $bf(n) \in O(f(n))$?

17 Views Asked by At

I'm looking up the definition of a smooth function which is composed of two parts:

  • The function must be eventually non-decreasing.
  • That $bf(n) \in O(f(n))$ must hold true for $b > 2$ and $b \in N$.

I have trouble convincing myself of the second statement but when really thinking about it this would mean that $bf(n) < cf(n)$ for the statement to be true. That implicitly means that $b$ must $< c$ at all times. How could this this be ensured?

1

There are 1 best solutions below

1
On

$$b f(n)=O(f(n))$$ is always true by definition.

$$\forall n: bf(n)\le bf(n).$$

If you prefer a strict inequality (though this is not mandated),

$$\forall n: bf(n)<(b+1)f(n).$$