0

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)

Ash
  • 375
  • 1
  • 3
  • 14

1 Answers1

0

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!
OmG
  • 18,337
  • 10
  • 57
  • 90