שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2025 - מיון

נתון מערך $A$ בגודל $n$. המערך מכיל $O(\log(n))$ ערכים שונים, שאינם ידועים מראש. הוכיחו שלא קיים אלגוריתם למיון המערך בזמן $O((\log(n))^2)$.

רמז: חשבו על חסם תחתון טריוויאלי: כל אלגוריתם מיון צריך לכל הפחות לקרוא את כל הקלט.

פתרון: לכל הפחות צריך לעבור על כל הקלט, כלומר יש חסם תחתון ליניארי $\Omega(n)$ לבעיה. מכיוון ש: $$(\log n)^2 = o(n)$$ (כי לכל קבוע $k$, $(\log n)^k = o(n)$), אלגוריתם בזמן $O((\log n)^2)$ לא יכול אפילו לקרוא את כל $n$ איברי הקלט. לכן לא קיים אלגוריתם למיון המערך בזמן $O((\log(n))^2)$.