I have been trying to learn Big O complexity and I read multiple resources including the answer given by dheeran with a graph.
Polynomial time and exponential time
I have few doubts of my own and few new doubts are raised after reading the answer below because it was not descriptive and clear.
Note: n is large (in billions)
Q1. I have read that, for any c > 0, log n is O(n^c). My understanding of Big O is log n will always be less than n^c for any value of c. So, check this example:
c = 0.000001
n = 1,000,000,000 i.e 1 billion
=> n^c = 1.00002072348
=> log(1 billion) = 9
So how come log n > n^c when log n is O(n^c)
Q.2 As mentioned in the answer, the order of increasing complexity is:
O(1),O(log n),O( (log n)^c ),O(n),O(n^2),O(n^c),O(c^n),O(n!)
If 0 < c < 1 eg. 0.001 Would the order change or still be:
-O( log n ),O( (log n)^c )
-O(n^c),O(c^n)
-O(n),O(c^n)
Here "in billions" means large enough. Hence, it depends on functions. To prove that you need an n0, and it can be 10^20 here, in your example.
Also, as c is a constant, you can choose n0 base on the value of c. For example, if c < 1, you can choose n0 = 10^{10/c}. So, for all n > n0, n^c is greater than log(n).
For the second question, definitely for 0 < c <= 1, c^n is less than all those, as it goes to zero for bigger n! and log(n)^c is in O(log(n)). Therefore the order is:
c^n, 1, (log(n))^c, log(n), n^c, n, n^2, n!