Cara - 5 months ago 11x
Java Question

# Order of the growth of these expressions?

I don't understand order of growth all that well, and I'm stuck on a book problem. Any explanation or help would be greatly appreciated. The question is:

For the following expressions, what is the order of the growth of each?

n^2 + 2n + 1

n^10 + 9n^9 + 20n^8 + 145n^7

(n + 1)^4

n + log(n)

(n^3 + 2n)/(n^2 + 0.75)

I didn't list all of them because I just want to get an idea or understand how to do them. Thanks!

Here is a table showing the Big-O complexities for each of your expressions. I think this is what you want when you say "order of the growth of each":

``````Expression                      Complexity
------------------------------------------
n^2 + 2n + 1                    O(n^2)
n^10 + 9n^9 + 20n^8 + 145n^7    O(n^10)
(n + 1)^4                       O(n^4)
n + log(n)                      O(n)
(n^3 + 2n)/(n^2 + 0.75)         O(n)
``````

One simple rule to keep in mind when computing Big-O complexities is what will happen to the expression as n approaches infinity. For example, consider your first expression n^2 + 2n + 1. When `n` becomes sufficiently large, the `n^2` term will dominate the behavior of the expression.

Source (Stackoverflow)