টাইম কমপ্লেক্সিটি হল একটি অ্যালগরিদমকে তার গড় কেসে রান করার জন্য প্রয়োজনীয় সময়।
আইये কিছু বেসিক ফাংশনের টাইম কমপ্লেক্সিটি ক্যালকুলেট করি।
মেথড ১
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 বার এবং শেষ ইটারেশনের জন্য ১ বার।
এনुसারে, মোট টাইম কমপ্লেক্সিটি:
(n/1 + n/2 + n/3 + ... + n/n) = n (1/1 + ½ + ⅓ + ... + 1/n)
এখন (1/1 + ½ + ⅓ + ... + 1/n) এর মান সমান O(log n)।
এই কোডের টাইম কমপ্লেক্সিটি O(n log n)।
মেথড ২
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!)。
