समय की जटिलता एल्गोरिथम द्वारा अपना औसत केस चलाने के लिए आवश्यक समय के रूप में परिभाषित किया जा सकता है।
आइए कुछ बुनियादी कार्यों की समय जटिलता को देखें और उनकी गणना करें।
विधि
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;
}
}
} फ़ंक्शन की कुल जटिलता ओ (लॉग 1) + ओ (लॉग 2) + ओ (लॉग 3) +… है। + ओ (लॉग एन) जो ओ है (लॉग एन!)।