Cara Cara - 1 year ago 87
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!

Answer Source

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.