دنباله‌ی $a_1, a_2, \dots, a_n$ از اعداد طبیعی مفروض است. به $n^k$ طریق می‌توان یک $k$ تایی مرتب از این اعداد تولید کرد. به ازای هر یک از این $k$ تایی‌های مرتب، جمع آن را در دنباله $s$ قرار می‌دهیم (جمع یک $k$ تایی مرتب برابر با مجموع تمامی اعضای آن می‌باشد).
دنباله $s$ که به صورت نانزولی مرتب شده است را $s_1 \leq s_2 \leq \dots \leq s_{n^k}$ در نظر بگیرید. الگوریتمی بیابید که با ورودی گرفتن $n$ ،دنباله‌ی $a$ و عدد $m$ مقدار $s_m$ را مشخص کند ($k$ مقداری ثابت است).
اگر الگوریتم شما از $O(n^{\lceil \frac{k}{2} \rceil} lg(n) lg(max(a_i))$ باشد ۱۵ امتیاز، اگر از $O(n^{\lceil \frac{k}{2} \rceil} lg^2(n))$ باشد، ۸۰ امتیاز و اگر از $O(n^{\lceil \frac{k}{2} \rceil} lg(n))$ باشد ۱۰۰ امتیاز می‌گیرید.

باید ثابت کنید الگوریتم شما درست و از مرتبه مشخص شده است. توجه کنید که حافظه اشغال شده توسط الگوریتم شما از مرتبه پیچیدگی زمانی آن باشد.

• سوال قبل