Pokazują, że $(\log n)^{\log n}\in\Omega (n)$

Nov 20 2020

Pokazują, że$(\log n)^{\log n}\in\Omega (n)$

Przechodząc do wspólnej własności logarytmicznej, otrzymujemy$$(\log n)^{\log n}=(n^{\log\log n})$$

Jak mam to wywnioskować?$$(n^{\log\log n})\in\Omega(n)$$

Jeśli tak powiem$n=b^{b}$gdzie$b$czy podstawa logarytmu może być prawdziwa, ale czy nie przekreśla celu bycia liniowym?

Tutaj,$\Omega,\Theta,\mathcal{O}$są dobrze znane asymptotyki, tj. dolna granica, górna granica i duże O .


Zostało to znalezione w MIT 6.006 wiosna 2020 , pytanie numer 6, chociaż przyjęto podstawę$2$logarytm.

Odpowiedzi

2 Adam Nov 20 2020 at 01:04

Kiedy$n$jest wystarczająco duży,$\log \log n \geq 1$. W związku z tym$n^{\log \log n} \geq n^1 = n$dla$n$wystarczająco duży.