Thread: Order of growth

Hi!

We recently started Time complexity/order of growth in my computer science class, and we were given a table with a number of different order of growth definitions ((O)N^2, O(N^3), O(N!), etc...) So, I haven't seen a definition describing anything like N^9 or N^8. What kind of order of growth would we classify something like n^10 + 9n^9 + 20n^8 + 145n^7?

2. In the case of something like n + 0.001n^3, where the higher n power is multiplied by a small number, would that still be O(N^3), or not?

Thanks a lot!

O(n^10 + 9n^9 + 20n^8 + 145n^7) == O(n^10)
O(n + 0.001n^3) == O(n^3)

The run time analysis only cares about the largest exponent. If n is going towards infinity the importance of smaller exponents becomes insignificant.
Or to phrase it differently, if we assume the following function:
n + C * n^2
Then for every constant C > 0 that you can imagine I can find an n, so that C * n^2 > n.
No matter how close your C is to 0, the quadratic growth is still superior to the linear growth when looking at large enough n.