eProstuti
স্বাগতম শিক্ষার্থী!

অনলাইন কোর্স ও পরীক্ষায় অংশ নিতে লগইন করুন

লগইন / রেজিস্টার
ওয়েবসাইট মেন্যু
14 Oct, 2026
#90255
নৈর্ব্যক্তিক (MCQ)

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

সঠিক উত্তর
O(n2)
বিস্তারিত ব্যাখ্যা ও সমাধান:

এখানে সঠিক উত্তর হলো $O(n^2)$।

র‍্যান্ডমাইজড কুইকসর্টে পিভট (Pivot) র‍্যান্ডম বা এলোমেলোভাবে নির্বাচন করা হলেও, ব্যাড লাক বা দুর্ভাগ্যের বশে যদি প্রতিবারই সবচেয়ে ছোট বা বড় উপাদানটি পিভট হিসেবে নির্বাচিত হয়, তবে কুইকসর্ট তার সবচেয়ে খারাপ পারফরম্যান্স বা ওর্স্ট কেস (Worst-case) এ পৌঁছে যায়।

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

শেয়ার করুন:
Support
Curiosity AI Assistant
24/7 লাইভ
eProstuti ডেটাবেস ও অটোমেশন ইঞ্জিন
এআই চ্যাট WhatsApp Messenger Instagram
👋 আসসালামু আলাইকুম শিক্ষার্থী !

আমি eProstuti Curiosity AI। আমাদের সকল লাইভ কোর্স, মডেল টেস্ট, ই-বুক, নোটিশ এবং পেমেন্ট সংক্রান্ত তথ্য নিমেষেই জানতে পারবেন।

দ্রুত উত্তরের জন্য নিচের টপিক চাপুন অথবা নিচে লিখুন:

উত্তরের তথ্য বিশ্লেষণ করা হচ্ছে...
eProstuti AI সহকারী
সার্বক্ষণিক সহায়তায় প্রস্তুত
লগইন আবশ্যক

ব্যক্তিগত সহায়তা এবং আপনার কোর্স, পরীক্ষা ও পেমেন্ট হিস্ট্রি দেখতে অ্যাকাউন্টে লগইন করুন।

* চ্যাটবট সরাসরি অ্যাকাউন্ট তৈরি বা লগইন করতে পারে না।