Order of Growth Definition

226 Views Asked by At

According to this book (section 3.1 Order of growth): An order of growth is a set of functions whose asymptotic growth behavior is considered equivalent. 

I'm trying to find more precise definition about order of growth. If I understand author's definition correctly he meant the following:

Order of growth of f(n) function is a set of all functions, such that the following statement is always true:

$$ \lim_{n\to \infty} \frac{f(n)}{C*g(n)} = 1 $$

where $C > 0$

Therefore, if $f(n) = 12 * n^2 + n + 14$ then order of growth can be any of the following functions:

$$g(n) = n^2$$ $$g(n) = 12*n^2$$ $$g(n) = 12*n^2 + 1$$ $$g(n) = 12*n^2 + log_2n$$ $$etc$$

So, basically I think it will be correct to say that the order of growth of f(n) function is just it leading term without a constant: $$f(n) = 12 * n^2 + n + log_2n$$ Order of growth of $f(n)$ $$g(n) = n^2$$

The question is: Is my reasoning are correct?