I have the following question:
Suppose algorithm A is able to solve a computational problem with input size N=100 in 0.5ms (milliseconds).
If the algorithm has a running time $\in O(N \log_{2}N)$ then how large a problem can it solve in 1 minute?
My approach to the problem currently is as follows:
let $t = (0.0005s) = (0.5ms)$, then: $\frac{t}{(100)log_{2}100} = \frac{(12*10^4)t}{(x)log_{2}x}$
where x is unknown input size that A can solve in 1 minute
this implies: $(x)log_{2}x = \frac{(100)log_{2}100(12*10^4)t}{t} = log_{2}100(12*10^6)$
now let $y = log_{2}x$ then the equation $(x)log_{2}x = log_{2}100(12*10^6)$ becomes:
$y2^y = log_{2}100(12*10^6) \Longrightarrow y2^y - log_{2}100(12*10^6) = 0$
Now at this point my plan is to use Newton's method for approximating roots (https://en.wikipedia.org/wiki/Newton%27s_method) to determine a solution for $y$ in the above equation.
Then once I have $y$ I just solve for $x$ (since $x = 2^y$)
My issue with this approach is the initial guessing I would have to make using Newton's method. I feel like there's no way to carry out this approach without using a calculator to calculate ridiculously large powers of 2 and that there must be a more elegant approach to this question. Is there a better approach I haven't explored yet?
Your approach makes sense. If you are applying Newton's Method programmatically, I would keep the original equation $x \lg x - M = 0$ where $\lg x = \log_2 x$. To guess the initial value, note that for large $M$ you also expect large $x$, and you certainly have $\lg x \le x$ so $x \le x \lg x \le x^2$ so $x_0 = \sqrt{M}$ is a good lower bound and $x_0 = M$ is a good upper bound. You can start with either one or their average.
In terms of the recurrence relation, we have $f(x) = x \frac{\ln x}{\ln 2} - M$ and $f'(x) = \frac{\ln x}{\ln 2} + \frac{1}{\ln 2} = \frac{1+ \ln x}{\ln 2}$ so $$ \frac{f(x)}{f'(x)} = \frac{x \frac{\ln x}{\ln 2} - M}{\frac{1+ \ln x}{\ln 2}} = \frac{x \ln x - M\ln 2}{1+ \ln x} $$ and the recurrence is $$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$ which you can program in Python or MATLAB etc.