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

I think开发者_开发技巧 NlogN and Nlog(N^2) are equivalent, and Nlog(logN) has a better RT than NlogN and Nlog(N^2). Can anyone confirm?

---

N*log(N^2) = 2N*log(N)

2N*log(N) is equivalent to N*log(N) (when it comes to big O notation, constant is skipped). NLog(logN) grows slower (has better runtime performance for growing N).

---

No. Big O notation has nothing to do with actual run time. O(n) can run shorter than O(1) for a given n value depending on the actual implementation.

Big O notation is about comparing how algorithms scale. Meaning as n increases, how much do they change relative to each other.

So, an example:

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

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

I know these functions can be reduced to x+100 and 2 * x respectively, but for demonstration purposes they are simple and show what we want them to. (and some compilers may actually optimize them, so there may not be a difference depending on your environment).

Now, add100(x) has an algorithmic complexity of O(1). And double(x) has a complexity of O(n). However, for values of x < 100, twice(x) will be faster than add100(x). For arbitrary input it won't. It won't scale as well, but it is faster for some range of input. Now, this is a trivial implementation, and not all algorithms will have a faster input range, but it does demonstrate that O() notation has no effect on actual runtime...

However, in this particular case, it's simple logarithm math. So Log(m^n) == n * Log(m), therefore n log(n) == log(n^n). So n log(n) != n log(n^2)... However, since constants are dropped in big O notation, n log (n^2) will transform to 2n log (n) which transforms to n log (n)... So n log(n) == n log(n^2) for the purposes of Big O notation...

---

Since log(n^2) = 2log(n), n*log(n^2) = 2n*log(n), which is equivalent to n*log(n).

And log(log(n)) < log(n), so n*log(log(n) < n*log(n).

You should just trust the basic properties of the logarithm function.

---

Yes, you are right if you are comparing in big O notation. Using the properties of logarithms, log n^2 == 2 * log n, so they are equivalent in big O. The log log n function grows strictly more slowly than log n.