שאלת מבחן במבוא למדעי המחשב - אוניברסיטת תל אביב 2020 - רקורסיה

בהמשך לפונקציית `edit_distance` שחישבה מרחק עריכה רקורסיבית: ב. מה מהטענות הבאות היא נכונה והרגילה לגבי סיבוכיות הזמן של הפונקציה? (i) הסיבוכיות היא קבועה (ii) הסיבוכיות היא ליניארית (iii) הסיבוכיות היא ריבועית (iv) הסיבוכיות היא אקספוננציאלית (v) אף תשובה אינה נכונה

רמז: בכל קריאה רקורסיבית (כאשר התווים שונים) יש 3 קריאות רקורסיביות.

פתרון: (iv) הסיבוכיות היא אקספוננציאלית. הסבר: בכל רמת הרקורסיה (כאשר התווים שונים), מבוצעות 3 קריאות רקורסיביות. העומק המקסימלי הוא $n+m$ (אורכי המחרוזות). לכן הסיבוכיות במקרה הגרוע היא $O(3^{n+m})$ שהיא אקספוננציאלית.