שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2020 - סיבוכיות

קבעו את היחס האסימפטוטי בין $(\log n)!$ לבין $n^k$ עבור $k$ קבוע חיובי כלשהו.

רמז: השתמשו בקירוב סטירלינג: $m! \approx \sqrt{2\pi m}(m/e)^m$, כאשר $m = \log n$. השוו באמצעות לוגריתם.

פתרון: נסמן $m = \log n$, כך ש-$n = 2^m$. נרצה להשוות $(\log n)! = m!$ מול $n^k = 2^{km}$. ניקח לוגריתם (בסיס 2) משני הצדדים: $\log(m!) = \sum_{i=1}^{m} \log i = \Theta(m \log m)$ (מנוסחת סטירלינג). $\log(n^k) = k \log n = km$. נשווה: $m \log m$ מול $km$. מכיוון ש-$\log m \to \infty$ כאשר $m \to \infty$, הרי שלכל $k$ קבוע, מתקיים $m \log m \gg km$ עבור $m$ גדול מספיק. לכן $\log(m!) \gg \log(n^k)$, כלומר: $$n^k = o((\log n)!)$$ במילים אחרות: $(\log n)!$ גדל אסימפטוטית מהר יותר מ-$n^k$ לכל $k$ קבוע חיובי.