با سلام
اول از لحاظ مفهمی:
وقتی میگه حالت متوسط یعنی میتونه مرتبه یا هزینه ما بیشتر از این مقدار هم بشه اما وقتی میگه همیشه یعنی چه در در حالت بدترین و چه در حالت متوسط یا بهترین همیشه همین مقدار را باید هزینه کنیم.
و اما در ادامه ...
بگذارید اینجور توضیح بدم که فرض کنید این همان الگرویتم مرتب سازی سریع است .
توضیح: در مرتب سازی سریع ما تا زمانی که به ارایه های تک عضوی برسیم مراحل تقسیم و پارتیشن بندی را انجام میدهیم .
حال اینطور تصور کنید که این الگوریتم وقتی به ارایه هایی به طول [tex]\frac{N}{K}[/tex]
رسید دیگر پارتیشن بندی را متوقف کرده و کار تمام شده است .
محاسبه پیچدگی:
در این الگروریتم هر بار هزینه پارتیشن بندی را داریم [tex]O(n)[/tex]
اما عمق درخت از Lgn به Lgk کاهش پیدا میکند زیرا:
تعداد گره‌ها در برگها برابر با [tex]\frac{N}{K}[/tex] میباشد .(در مرتب سازی سریع تا ۱ پیش میرفتیم )و لذا داریم: :

[tex]\frac{N}{2^{h}}= \frac{N}{K} \Rightarrow h=log(k)[/tex]

و در نهایت همیشه مرتبه ان برابر است با‌ ::[tex]Nlog(k)[/tex]

نکته اخر بر سر اختلاف نظر بزرگان در حل این تست:
همانطور که میدانید کارایی مرتب سازی سریع به نحوه پارتیشن بندی بستگی دارد اگر پارتیشن بندی به طرز مناسبی صورت گیرد لذا مرتب سازی سریع همیشه nlgn است و همانطور که میدانید در بدترین حال از مرتبه ۲ است اما الگوریتمهایی وجود دارندکه با انتخاب عنصر محور مناسب جهت پارتیشن بندی (روش میانه سه و یا انتخاب تصادفی) همواره هزینه nlgn را دارند و لذا هزینه ان همیشه nlgn است (برای اثبات قضیه به کتاب Clrs مراجعه کنید.)
تمام ماجرا همین بود
موفق باشید.

جواب این سوال گزینه ۱ میشه حالا چرا؟
nعنصر داریم که میخواهیم آنها رابهkمجموعه پارتیشن کنیم که همه عناصر مجموعه اول از همه عناصر مجموعه دوم،همه عناصرمجموعه دوم از همه عناصر مجموعه سوم و...کوچکترهستند.برای اینکار ابتدا میانه راپیداکرده که هزینه آنO(n وروی آنpivot میزنیم دراینصورت همه عناصر سمت چپ ازآن کوچکتر وهمه عناصرسمت راست ازآن بزرگترهستند(درواقع انکاردوتا مجموعه ساختیم)سپس دوباره همین اعمال را روی زیر آرایه‌ها انجام میدیمیعنی میانه هرزیر آرایه رابدست میاوریم وتا آخر...وقتی kتا مجموعه داریم باید log k بار آرایه رابشکنیم وچون هزینه هر سطرO(n پس در مجموع همیشه از مرتبهnlogkهست.امیدوارم متوجه شده باشید.