写[(m + n)^ m ] /m有效吗？以O([n / m]^m)为其松散的上界？

Question

在将(m + n)^m / m!的上界写入O(n / m^m)时，考虑了m！= O(m^m) .

Answer 1

正如你所说的，m!是o(m^m)。因此，您不能在A = (m+n)^m / m!中替换它以获得上限！相反，你可以使用Stirling的近似得到一个适当的上界。正如我们所做的(参见这里)：

m! = \sqrt{2\pi m} (m/e)^m (1 + O(1/m))

您可以通过将A替换为m!，从而得到(m/e)^m的上限。因此：

A < (n+m)^m / (m/e)^m = (e*(n+m)/m)^m = (e * (n/m + 1))^m

如果是n > m，我们知道(n/m + 1)^m = Theta((n/m)^m)。因此，A \in O(e^m (n/m)^m)