我有一个算法 n为数组的长度。 和binary_search的（阵列，O，N值）的T（n）是T（N）=西塔（LGN）。

I got a algorithm n is array's length. and binary_search(array, 0, n, value) 's T(n) is T(n) = Theta(lgn).

CHECK_VALUE_IN_ARRAY(array, n, value)
for i = 1 to n
    binary_search(array, i, n, value)

如何获取T（n）的？ 下面是我的步骤：

how to get T(n) ? Here is my steps:

T(n) = c(lg(1) + lg(2) + lg(3) + ...+ lg(n)) 
    = clgn!
    = Theta(lgn!)

这是正确的？

Is this right?

2）如果这是正确的？    谁更快增长？    nlgn VS LGN！

2) If this is right? Who grows faster? nlgn vs lgn!

非常感谢你。

推荐答案

对于大型 N 两者是相同的，更多的precisely它们的比值收敛于1更precisely，你大概

For large n both are identical, more precisely their ratio converges towards 1. Even more precisely, you have roughly

log(n!) == n*(log(n)-1)

如果你想准确的说，你会发现

If you want to be exact, you will find

log(n!) == n*(log(n)-1) + 1/2*log(2*Pi*n) + O(1/n)

编辑：：一种很好的来源，这是wolframalpha.com，要求系列（！的log（n））

A good source for this is wolframalpha.com , ask for Series(Log(n!))