לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

1[עריכה]

הטענה נכונה.

ברור שזמן הריצה של Foo(n) לפחות גדול כמו זמן הריצה של Bar(n). לכן נקבל . אבל , ולכן הטענה נובעת מטרנזיטיביות.

2[עריכה]

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

נניח שזמן הריצה של Bar-1(n) הוא , זמן הריצה של Bar-2(n) הוא , וזמן הריצה של Bar-3(n) הוא . (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, . הטענה בבירור מתקיימת.


לחלופין, נניח שזמן הריצה של Bar-1(n) הוא , זמן הריצה של Bar-2(n) הוא , וזמן הריצה של Bar-3(n) הוא . (קל לראות שנתוני השאלה מסופקים.)

אז במקרה זה, . קל להראות (באופן דומה לזה שראינו בתרגילים קודמים) שלא ייתכן שבמקרה זה .

3[עריכה]

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

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