ראינו שלשום בתרגול שאפשר לבדוק אם יש איבר במערך שחוזר n/lgn פעמים בזמן קצר יותר אסימפטוטית מ-Theta(nlgn).
נעשה שימוש ב-Quick sort חכם (לפי מיטב הבנתי, נק' ה-pivot בכל שלב היא ה-median, אותו מוצאים בזמן Theta(N) ע"י שימוש ב-Select).
אבל עוצרים את האלגוריתם כאשר מגיעים לתת-מערכים מגודל n/lgn.
השאלה היא, מה בדיוק עושים מכאן? ניסיתי לראות איך אפשר לבדוק ביעילות אם איבר חוזר על עצמו n/lgn פעמים.
מה שאני מבין זה שהמערך "כמעט ממוין", כלומר כל תת-מערך קטן מזה שמימינו. אבל עדיין אני לא בדיוק רואה מכאן מה ניתן לעשות.
תודה.