স্টেপ কাউন্ট মেথড হল অ্যালগরিদম বিশ্লেষণের একটি পদ্ধতি। এই মেথডে, আমরা একটি ইনস্ট্রাকশন কতবার এক্সিকিউট হচ্ছে সেটি কাউন্ট করি। তার থেকে আমরা অ্যালগরিদমের কমপ্লেক্সিটি বের করার চেষ্টা করি।
ধরা যাক আমাদের একটি অ্যালগরিদম রয়েছে সিকোয়েনশিয়াল সার্চ করার জন্য। ধরা যাক প্রতিটি ইনস্ট্রাকশন c1, c2, ... টাইম নেয় এক্সিকিউট होने, তাহলে আমরা এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি বের করার চেষ্টা করব।
| 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 |
c1 c2 c3 c4 c5 |
এখন যদি এক্সিকিউশন সংখ্যা দিয়ে কস্ট গুণ করে যোগ করি (ওয়ার্স্ট কেস বিবেচনা করে), তবে পাব -
Cost = c1 + (n+1)c2 + nc3 + c4 + c5
Cost = c1 + nc2 + c2 + nc3 + c4 + c5
Cost = n(c2 + c3) + c1 + c4 + c5
Cost = n(c2 + c3) + C
c1 + c4 + c5 কে C ধরে, ফাইনাল সমীকরণ সোজা রেখা y = mx + b-এর মতো। সুতরাং ফাংশনটি লিনিয়ার। কমপ্লেক্সিটি হবে O(n)।
