חסמים אסימפטוטיים של פונקציות

[ohad]

נתנו לנו 14 (!) פונקציות שונות ומשונות ובקשו לסדר אותם מהקטנה לגדולה (אסימפטוטית) ולהוכיח שאחת היא O של השנייה וכו'.
נשארתי עם הארבע פונקציות הללו:

f_1=3^n,f_2=3^{2^n},f_3=(loglogn)^{logn},f_4=\Pi_{i=2}^n log(i)

ברור לי ש

f_1=O(f_2)

אבל לא ברור לי איפה ואיך לפתח את שתי האחרות, נראה לי שהן באמצע (כי n בחזקת n למשל בינהן),
רעיונות?

(תוספת: אני יודע ש

f_4=O((logn)^n)

אבל איך לחסום אותה מלמטה לא ברור לי)

[radagast]

אני לא כל כך מבין בזה, אבל אני דווקא חושב ש-f3 לא שייך לשם, הוא log של log (לוג של לוג של 1 ו-19 אפסים זה פחות מ-4, למשל), זו פונקציה שמתקדמת לאט מאד, והיא בחזקת logn, לא בחזקת n.

בנוגע ל-f4, החל מ-n כלשהו תקבל שהלוג כבר גדול ממספר כלשהו, למשל, עבור n=21 הוא כבר גדול מ-3, ואפשר לחסום אותו מלמטה ע"י [tex]3^n[/tex].

[ohad]

תודה, זה בערך מה שעשיתי בסוף,
f3 באמת קטנה יותר וחסמתי ככה ממטה את f4. 

נגמר התרגיל