1
$\begingroup$

So, in the book I'm studying from it says :

The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).

What I understood from this statement is that since 9n is O(n), the growth rate of the functions 9n and n have the same growth rate, which does not make sense. I know that growth rate is the increase of a certain quantity over time. So, obviously the function 9n will grow way faster towards infinity, than the function n.

Did I understand the sentence given in the book incorrectly or is the statement incorrect?

$\endgroup$

1 Answer 1

1
$\begingroup$

You understood it correctly, but have interpreted it differently than the book wanted it to be interpreted. You are right that $9n$ grows faster than $n$ so the main problem in your book may be trying to express a mathematical definition of $O$ with too few words.

The definition
The function $f(n)$ is in $O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and a positive real number $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Now it is clearer how $9n$ is in $O(n)$. Because there exist, say $c=10$ and $n_0=0$ such that $9n \leq c \cdot n$ for all $n \geq n_0$.

Why compare so loosely?
The problem is, if we would compare growth rates by exact function values, then two very similar functions may not end up in the same class. For example, with your "strict-O notation"; for any function $d > 0$, $f+d$ would not be in the same class as $f$, and that is not very useful. So, we have to draw the line somewhere (pun intended). Also, we use asymptotic analysis for describing algorithm complexity dependant on the input size $n$, and it is often not possible to calculate computation steps that precise.

Other notations
But, there are other asymptotic notations except big-O so you might want to look at those. You will find that $\Theta$ is, for example, more restrictive than $O$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.