Step Count Method
นับจำนวนครั้งที่แต่ละ Instruction ทำงาน เพื่อหา Time Complexity
ตัวอย่าง: Sequential Search
| Algorithm | Number of Times | Cost |
|---|---|---|
| seqSearch(arr, n, key) i := 0 while i < n, do if arr[i] = key, then break end if done return i |
1 n+1 n 0/1 1 |
c₁ c₂ c₃ c₄ c₅ |
การคำนวณ Worst Case
Cost = c₁ + (n+1)c₂ + nc₃ + c₄ + c₅
= n(c₂ + c₃) + (c₁ + c₄ + c₅)
= n(c₂ + c₃) + C
เป็นสมการเส้นตรง y = mx + b → Complexity = O(n)
