[M@gpie]

พอดีเห็นคุณ <เสริม> พูดถึงอ.ซึง เลยนึกขึ้นได้ไปค้นๆมา เห็นแต่ที่คล้ายๆนะครับ
ความสัมพันธ์ recurrence ของ Binary search เป้นดังนี้
T(n)=T(n/2)+C₂
ให้ T(1)=C₁
solving the recuurence relation ดังนี้
T(n)
= C₂+T(n/2)
= C₂+ C₂ +T(n/4)
= C₂+ C₂+ C₂T(n/8)
... ลองแทนความสัมพันธ์ไปเรื่อยๆจะได้หน้าตาแบบนี้
T(n)=i C₂ +T(n/2ⁱ)
เมื่อ 2ⁱ=n จะได้ว่า i=log₂n
แทนค่า i ลงไปจะได้ว่า
T(n)=(log₂n)C₂ +T(1)=C₂(log₂n)+C₁
เป็นปัญหาด้านคอมพิวเตอร์นะครับอยู่ในส่วน Alglorithm