السلام عليكم ...

في هذا الـ code ...

for (int i = 1; i < n; i *= 2)
	 ++k;

في حالة i*=2 فإن الـ Time Complexity سيكون log n للأساس 2 وفي حالة i *= 10 سيكون log n للأساس 10 ولكن ما هي طريقة عملها و من أين جاءت؟

قبل أن أبدأ تذكرة سريعة بالـ Logarithm:

Log2 (2^n) = n
Log10 (10^n) = n
Log2 (2*2*2*2 ……. n times) = Log2 (2^n) = n

حسناً الآن دعنا نعيد ترتيب الحلقة بالشكل التالي:

for (int i = n; i >= 1; i /= 2)
	 ++k;

ببساطة لقد قمت بقلب الحلقة. فبدل أن تبدأ بـ 1 وتنتهي بـ n أصبحت تبدأ بـ n وتنتهي بـ 1.
الآن وباعتبار أن ترقيم التنفيذ يبدأ من 0 فإنه:
ملاحظة: حاول قراءة الأسطر التي تحاذي اليسار من اليسار إلى اليمين حتى ولو كانت عربية. أعتذر عن سوء التنسيق

- في التنفيذ رقم 0 تكون i مساوية لـ n
- في التنفيذ رقم 1 تكون i مساوية لـ n/2
- في التنفيذ رقم 2 تكون i مساوية لـ
(n/2)/2 أي n/4 وبمعنىً آخر n/(2^2)

- في التنفيذ رقم 3 تكون i مساوية لـ
(n/4)/2 أي n/8 وبمعنىً آخر n/(2^3)
.
.
- في الـتنفيذ رقم k تكون i مساوية لحاصل قسمة n على 2 k مرة أي
n/2/2/2 …. k times)) بمعنىً آخر n/(2^k)
.
.
- في التنفيذ الأخير (وليكن رقمه m) تكون i مساوية لـ 1 وبمعنىً آخر
n/(2^m)
مهمتنا هي أن نحسب المجهول m والذي يعبر عن عدد مرات التنفيذ

n / (2 ^ m) = 1
n = 2^ m
log2(n) = m		بأخذ "لوغاريتم" الطرفين

أي أن عدد مرات التنفيذ هو m=log2(n) وهو الـ Time Complexity
بالطبع يمكن الوصول لنفس النتيجة باستخدام الأساس 10