اینم یه سوال از نوع تحلیلی
[tex]\frac{2^{0} 2^{1} .. 2^{n} 2^{n}-n}{2^{n}}=\frac{2^{n 1}-1 2^n-n}{2^n}\approx 3[/tex]
بله درسته چون ما n+1 عمل داریم که توانی از ۲ باشند از [tex]2^0[/tex] تا [tex]2^n[/tex]
که مرتبه شون برابر خودشون هست و مجموعشون میشه [tex]2^{n 1}-1[/tex]
بقیه اعمال توانی از ۲ نیستند که تعدادشون میشه [tex]2^{n}-n[/tex]
و چون مرتبه هرکدوم ۱ هست میشه [tex]2^{n}-n[/tex]
اسم این روش روش سرشکن است.یعنی هزینه بالای اعمالی که توان ۲ هستند توسط هزینه پایین سایر اعمال (که تعدادشان بسیار زیاد است) سرشکن شده و به هزینه متوسط ۳ برای هر عمل میرسیم.