Skip to Content

Why is nlogn so hard to invert?

Lets say I have a function that is nlogn in space requirements, I want to work out the maximum size of input for that function for a given available space. i.e. I want to find n where nlogn=c.

I followed an approach to calculate n, that looks like this in R:

step = function(R, z) { log(log(R)-z)} 
guess = function(R) log(log(R))
 
inverse_nlogn = function(R, accuracy=1e-10) {
 zi_1 = 0
 z = guess(R)
 while(abs(z - zi_1)>accuracy) { 
  zi_1 = z
  z = step(R, z)
 }
 exp(exp(z))
}

But I can't get understand why it must be solved iteratively. For the range we are interested (n>1), the function is non singular.