Cara - 1 year ago 79

Java Question

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

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)