So, I have a problem I'm supposed to do in which I am supposed to put the following assertions in order according to order of growth
2nlogn
0.000001n^3
1983n^2 + n
n + 456
3^n + 5n
and I don't know how to go about doing this. I'm supposed to organize them in a fashion like 2nlogn <= n + 456 <= etc....
I'm not looking for the answer- I just need some advice on how exactly to do this. I know the order of growth table but it doesn't help me here.
If you know the order of growth table, that's mostly it!
The other big thing to know is that coefficients and lower order terms don't matter. For example,
3n^2 ~ n^2 > 1000n ~ n
If that's difficult to understand, imagine what happens as n becomes extremely large. n^2 grows quickly as n increases, while 1000n only increases by 1000 each time n increases by 1. By the time n=1000, then n^2 = 1000n, and as n increases even more, n^2 overtakes 1000n.
So, for any function like n^2 + 1000n, split it into different terms that are added together (multiplication is different, e.g. n*log(n) is different from n or log(n)). you can ignore everything but the largest term, in this case n^2. Once you do this and strip away coefficients, just use the order of growth table to get your solution!
https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions