I am reading a paper, and having a hard time determining how a result was obtained. The paper states that: Since the total number of linear-extensions is initially $n!$ and probing an edge reduces the number of linear-extensions by a $1-1/e \sqrt{n}$, then only $O(n^{3/2}log(n))$ probes are necessary. I was under the impression that this meant that I had to solve for $x$ in the following: $$n! = (1-1/e\sqrt{n})^x $$ right? If so, I tried using Stirling's approximation on $n!$ and took the logs of both sides, but only get a dominating term of $O(nlog(n))$.
This gives that: $x = \frac{nln(n) - n + O(ln(n))}{ln(1-1/e \sqrt{n})}$, which just seems to be $O(nlog(n))$. The context given isn't really important, as I am just stuck on the algebra.
You have $$\ln \left(1 - \frac{1}{e\sqrt{n}}\right) = -\frac{1}{e\sqrt{n}} + O(1/n),$$
since the Taylor expansion of the logarithm yields
$$\ln (1-x) = -\left(x + \frac{x^2}{2} + \frac{x^3}{3} + \frac{x^4}{4} + \dotsb \right).$$
So you get
$$x = \frac{\ln n!}{\ln\left(1-\frac{1}{e\sqrt{n}}\right)} = -e\cdot n^{3/2}\ln n + O(n^{3/2}).$$