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