対数を持つ調和級数の大きなシータ表記を見つける

2020-08-01 big-o complexity-theory

次の式の大きなシータまたは大きなO表記を見つけようとしています。

ここに画像の説明を入力してください

私はそれをこの表現に単純化しました:

ここに画像の説明を入力してください

しかし、今、私はこの表現をどうするかわからないので、助けてください。

Answers

T(n) = log(x) + log_2(x)/2 + log_2(x)/3 + ... + 2log_2(x)/x
Since x log(x) is common for all elements in summation:
T(n) = log(x) (1 + 1/2 + 1/3 + ... + 2/x)
                        ^
                     H(x/2)

T(n) = log(x)*H(x/2)

そして、H(x / 2)はTheta(x / 2)にあるので、 T(n)Theta(log^2(x))

Related