উত্তর সিলেক্ট করলে সঠিক ও ভুল দেখাবে।
ব্যাখ্যা ও সঠিক সমাধান
উত্তর:
O(n2)
এখানে সঠিক উত্তর হলো $O(n^2)$।
র্যান্ডমাইজড কুইকসর্টে পিভট (Pivot) র্যান্ডম বা এলোমেলোভাবে নির্বাচন করা হলেও, ব্যাড লাক বা দুর্ভাগ্যের বশে যদি প্রতিবারই সবচেয়ে ছোট বা বড় উপাদানটি পিভট হিসেবে নির্বাচিত হয়, তবে কুইকসর্ট তার সবচেয়ে খারাপ পারফরম্যান্স বা ওর্স্ট কেস (Worst-case) এ পৌঁছে যায়।
- এমনটা হলে রিকার্সন ট্রি এর গভীরতা সর্বোচ্চ হয়ে যায় এবং প্রতিটি স্তরে $n$টি উপাদানের তুলনা করতে হয়।
- ফলে মোট কাজের পরিমাণ দাঁড়ায় $n + (n-1) + (n-2) + \dots + 1 = \frac{n(n+1)}{2}$, যা বড় নোটেশনে সহজ কথায় $O(n^2)$।