Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is O(n^(1/logn)) actually constant?

Tags:

big-o

math

I came across this time complexity function and according to me, it is actually constant. Please correct me if I am wrong.

n^(1/logn) => (2^m)^(1/log(2^m)) => (2^m)^(1/m) => 2 

Since any n can be written as a power of 2, I can do the above simplification and prove that it is constant, right?

like image 859
Nirup Iyer Avatar asked Sep 11 '19 19:09

Nirup Iyer


People also ask

Is O log n same as O 1?

So no, O(1) and O(logn) are not the same.

Is O 1 in O LOGN )?

O(1) means the running time of an algorithm is independent of the input size and is bounded by a constant 'c'. Whereas, O(log n) means when input size 'n' increases exponentially, our running time will increase linearly.

What does the time complexity O log n actually mean?

Logarithmic time complexity log(n): Represented in Big O notation as O(log n), when an algorithm has O(log n) running time, it means that as the input size grows, the number of operations grows very slowly.

Which is better O log n or O 1?

→ At exactly 50 elements the two algorithms take the same number of steps. → As the data increases the O(N) takes more steps. Since the Big-O notation looks at how the algorithm performs as the data grows to infinity, this is why O(N) is considered to be less efficient than O(1) .


1 Answers

Assuming log is the natural log, then this is equivalent to e, not 2, but either way it's a constant.

First, let:

k = n^(1 / log n)

Then take the log of both sides:

log k = (1 / log n) * log n

So:

log k = 1

Now raise both sides to the power of e to get:

e^(log k) = e^(1)

And thus:

k = e.
like image 194
John Feminella Avatar answered Nov 24 '22 05:11

John Feminella