- הגשות
- פתרונות
- פתרון רשמי
- תיאור
מה מספר הקריאות לשגרת Random שמבצעת הפונקציה Randomized-Quicksort(A,1,n)? נמקו את תשובתכם באמצעות נוסחת נסיגה מתאימה ופתרו אותה.
שימו לב כי מספר הקריאות המדויק תלוי בבחירות האקראיות של האיבר לציר (pivot). לכן, יש לחשב את תוחלת מספר הקריאות. בכל קריאה רקורסיבית על תת-מערך בגודל הגדול מ-1, כמה פעמים נקראת השגרה Random?