Trouble isolating $R$ in equation $lnR - \frac{n+R}{R} = 0$ (minimizing Radix sort time)

36 Views Asked by At

The question asks to find the value of R to minimize the Radix sort time.

Radix sort complexity is $\Theta\left(\frac{\ln S}{\ln R}(n+R)\right)$ where S is range of the numbers to be sorted, R is the Radix, and n is the number of elements to be sorted.

I start off knowing that $t = a\left(\frac{\ln S}{\ln R}(n+R)\right)$ for some constant a and S, so I took the derivative and got $$\frac{dt}{dR} = \frac{a\ln S \times\left (\ln R - \frac{n+R}{R}\right)}{(\ln R)^2}$$ Then, I set equal to 0 and got $$\frac{\ln R-\frac{n+R}{R}}{(\ln R)^2} = 0$$ $$\ln R-\frac{n+R}{R} = 0$$ $$\ln R = \frac{n+R}{R}$$ I know the answer is $R = \frac{n}{\ln(n)}$, but I'm not sure how to isolate R from the above equation. Any help would be appreciated.