##### Which one has higher complexity? O(root(n)) or O(n/lon(n))

which has greater time complexity and how?

O(root(n)) or O(n/lon(n))

Pritam Prasun
16 Apr 2017 08:33 pm

$O(\frac{n}{logn})$ will have greater complexity. To realize this I suggest taking some numeric value of n and see yourself.

Parth Sharma
17 Apr 2017 08:15 am

root(n)  , n / logn can be written as  root(n)  and {root(n) * root(n) }/ logn

we can cancel root(n) from both and get    1, root(n)/logn

now  1 means constant  and  root(n)/logn is definitely increasing

so, n/logn has greater complexity .

we can do many things to proof ,this is among one of them.