שלום לכולם.
איך ניתן להוכיח או להפריך את הטענה הבאה:
n^{\log(c)}=O\left(c^{\log(n)}\right)
אשמח לעזרה,
תודה רבה.
הטענה נכונה. למעשה, מדובר בחסם הדוק, כלומר מתקיים:
n^{\log c}=\Theta\left(c^{\log n}\right)
נוכיח זאת:
n^{\log_b c} = \Big(b^{\log_b n}\Big)^{\log_b c} = b^{(\log_b n)(\log_b c)} = \Big(b^{\log_b c}\Big)^{\log_b n} = c^{\log_b n}
לכן, בפרט מתקיים n^{\log c}=O\left(c^{\log n}\right).