সময় জটিলতা অ্যালগরিদম এর গড় কেস চালানোর জন্য প্রয়োজনীয় সময় হিসাবে সংজ্ঞায়িত করা যেতে পারে।
আসুন কিছু মৌলিক ফাংশনের সময় জটিলতা দেখি এবং গণনা করি।
পদ্ধতি
void counter(int n){
for(int i = 0 ; i < n ; i++){
for(int j = 1 ; j<n ; j += i ){
cout<<i<<” ”<<j;
}
cout<<endl;
}
} উপরের পদ্ধতিটি i-এর সমস্ত মানের জন্য n/I বার চলবে। অর্থাৎ প্রথম পুনরাবৃত্তির জন্য n বার এবং শেষ পুনরাবৃত্তির জন্য 1 বার।
এই অনুসারে, মোট সময় জটিলতা হল
(n/1 + n/2 + n/3 + …. + n/n) = n (1/1 + ½ + ⅓ + …. 1/n)
এখন (1/1 + ½ + ⅓ + .... 1/n) এর মান O(log n) এর সমান .
এই কোডের সময় জটিলতা হল O(nlogn) .
পদ্ধতি
void counter(n){
int i , j ;
for(int i = 1 ; i <= n ; i++){
for(j = 1; j <= log(i) ; j++){
cout<<i<<” ”<<j;
}
}
} ফাংশনের মোট জটিলতা হল O(log 1) + O(log 2) + O(log 3) + …. + O(log n) যা O(log n!).
