How to solve O (N log N) and more

complexity

I got following exercise:

An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:

  1. linear
  2. O (N log N)

…

So the algorithm can process 100 items in 0.5 ms therefore 100*(2*1000*60) = 12 000 000 items processed for linear time.

Now how to solve 12 000 000 = O(N log N) for N?
N = 2^(12 000 000/N)

And I'm stuck with how to eliminate the exponential N.

Also the exercise goes on:

  1. Order the following functions by growth rate, and indicate which, if any, grow at the same rate.:

N, square root of N, N^1.5, N^2 , N log N, N log log N, N log^2 N, N log (N^2), 2/N, 2N, 2N/2, 37,N^3, N^2 log N

As I don't have any solutions as reference here is mine:

2/N < sqrt(N) < 37< N=2N/2 < 2N < N log log N < N log N < N log (N^2) < N log^2 (N) < N^1.5 < N^2 < N^2 log N

Would be cool if someone could have look at it and correct me where i might be wrong.

Best Answer

If your function is O (n ln n), you can assume that the exact time is c * n * ln n. Type the numbers for n = 100 into a spreadsheet and you get c = 0.5 ms / 100 / ln 100.

Type a formula into a spreadsheet and enter values for n until you get the solution.

You could do it in your head: If linear you could solve for n = 12 million. 12 million is about 100 ^ 3.5 so the logarithm is about 3.5 times larger so you divide by 3.5 giving about 3.5 million.

37 is between 2/n and n/2. Ln (n^2) is just 2 ln n. And you ignore constants when you look at growth orders.

To solve something like n ln n = 12000000 you change it to n = 12000000 / ln n. Then you start with n = 12000000, replace n with 12000000 / ln n, and repeat a few times. The trick is to write n = "something that shrinks". N = 2^(12000000/n) doesn't work.

Related Topic