Saying f = O ( g ) is a very loose analog of f <= g
It differs from the usual notion of because of the constant c , so that for instance 10 n = O ( n )
This came from my textbook how can 10n <= n when n is clearly below 10n on a graph?
I just started learning about big O notation and I am completely lost.
There is a good explanation at Why is constant always dropped from big O analysis? but we drop the constants.
Another way to think of it is that 10n is basically the same as n if you are a long way away and n is very large when you compare that function to other functions. n^2 is basically the same as 10n^2 when you compare these quadratic functions with the linear function we started with.
let n = 1,000,000. Then n = 1,000,000 and 10n = 10,000,000. n^2 = 1,000,000,000,000 and 10n^2 = 10,000,000,000,000
Now let n = 1,000,000,000,000. Then n = 1,000,000,000,000 and 10n = 10,000,000,000,000. n^2 = 1,000,000,000,000,000,000,000,000 and 10n^2 = 10,000,000,000,000,000,000,000,000,000,000
As n gets larger, a linear function with any constant will get closer and closer to the value of n compared to other classes of functions, and a quadratic function will get closer and closer to the value of n^2 compared to other classes of functions.
In our example, when n is 1 with a million zeros, who cares about one more zero in linear time because in quadratic time there's a million more zeros.
