תבנית:לאחד לתוך ולמחוק את הדף הנוכחי (שהינו דף תבנית!)
נגדיר את כקבוצת הצמתים שאליהם אפשר להגיע מ, ו כקבוצת הקשתות בין איברי צמתים אלה.
- 1-2 ו5-7 הן
- 3-4 הן .
- הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב. בפרט, הבדיקה ב8 והפעולה ב9 עולות .
- באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג כך ש. הלולאה תורמת לכן .
הסיבוכיות, לכן, היא .
כפי שנראה מיד, התשובה לסעיפים תלויה בפיזור הקשתות בין הצמתים ב.
הנה משפט עזר בו נשתמש:
משפט:
לכל ,
|
הוכחה: נשתמש בכללי גבולות וסדרי גדילה:
נניח ש הוא עץ (המסומן באליפסה בתרשים הבא), אך כל שני צמתים ב מחוברים בקשת.
מספר הקשתות בגרף הוא
הסיבוכיות היא רק , וקל לראות שביטוי זה אינו .
שוב נניח ש הוא עץ (המסומן באליפסה בתרשים הבא), אך כעת נניח שאין קשתות בגרף המקורי מעבר לקשתות אלו. במקרה זה הסיבוכיות תהיה מן הסתם
.