מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מציאת סיבוכיות פסוודו-קוד/תרגילים/פונקציה שקוראת לשלוש פונקציות אחרות/תשובה

נקרא לזמן הריצה של Foo(n) $\displaystyle f(n)$.

1

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל $\displaystyle f(n)\geq \Omega (n^{2}\log(n))\Rightarrow f(n)=\Omega (n^{2}\log(n))$. אבל $\displaystyle n^{2}\log(n))=\Omega (n)$, ולכן הטענה נובעת מטרנזיטיביות.

2

אי אפשר לקבוע אם הטענה נכונה או לא.

נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{4}$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{4}+1.2n^{2}+n=\Theta (n^{4})$. הטענה בבירור מתקיימת.

לחלופין, נניח שזמן הריצה של Bar-1(n) הוא $\displaystyle 10n^{2}\log(n)$, זמן הריצה של Bar-2(n) הוא $\displaystyle 1.2n^{2}$, וזמן הריצה של Bar-3(n) הוא $\displaystyle n$. (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, $\displaystyle f(n)=10n^{2}\log(n)+1.2n^{2}+n=\Theta (n^{2}\log(n))$. קל להראות (באופן דומה לזה שראינו בתרגילים קודמים) שלא ייתכן שבמקרה זה $\displaystyle f(n)=\Omega (n^{3})$.

3

אי אפשר לקבוע האם הטענה נכונה או לא.

שני המקרים מהסעיף הקודם מראים זאת.