مسالهیکتاسازی بدین شکل تعریف میشود:
اثبات کنید که هر الگوریتم یکتاسازی مبتنی بر مقایسه روی n عنصر از $\Omega(n\log n)$ است.
فرض کنید یک لیست مجاورت از یالهای یک گراف در اختیار داریم. الگوریتمی خطی $O(n+m)$ برای حذف یالهای تکراری در این لیست ارائه دهید. (نکته: درنظر گرفتن یک حافظه به طول $k$ زمان $O(k)$ لازم دارد)
آیا الگوریتم شما در قسمت ب، مثال نقضی برای اثبات قسمت الف نیست؟