java - Do Nlog(logN), NlogN, Nlog(N^2) have equivalent running times? -

i think nlogn , nlog(n^2) equivalent, , nlog(logn) has better rt nlogn , nlog(n^2). can confirm?

no. big o notation has nothing actual run time. o(n) can run shorter o(1) given n value depending on actual implementation.

big o notation comparing how algorithms scale. meaning n increases, how change relative each other.

so, example:

function add100(x) {     (i = 0; < 100; i++) {         x++;     }     return x; }  function twice(x) {     tmp = x;     (i = 0; < tmp; i++) {         x++;     }     return x; } 

i know these functions can reduced x+100 , 2 * x respectively, demonstration purposes simple , show want them to. (and compilers may optimize them, there may not difference depending on environment).

now, add100(x) has algorithmic complexity of o(1). , double(x) has complexity of o(n). however, values of x < 100, twice(x) faster add100(x). arbitrary input won't. won't scale well, is faster range of input. now, trivial implementation, , not algorithms have faster input range, demonstrate o() notation has no effect on actual runtime...

however, in particular case, it's simple logarithm math. log(m^n) == n * log(m), therefore n log(n) == log(n^n). n log(n) != n log(n^2)... however, since constants dropped in big o notation, n log (n^2) transform 2n log (n) transforms n log (n)... n log(n) == n log(n^2) for purposes of big o notation...