Comparing different time complexities
In this article, I'll try to give you folks a brief idea about how much time codes with different time complexities take to run when given different sizes of inputs.
Before diving in, I'd like to share that a C++ code can run around 2∗108 operations per second if those are low-level operations (array accesses, additions, bit-shifts, multiplies, subtractions, xors, etc.). Mods and divisions are slightly slower. Taking input & printing output is slightly even slower.
Of course, the number of operations per second depends on the machine, but the above-shared number is just a bare minimum that you can safely assume.
For example, my M2 Pro 14" Macbook Pro (subtle flex 😉) was able to run the code below in just less than 0.1 sec.
C++ Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
clock_t start, end;
int N = 2e8; // 2e8 means 2*10^8
int random = 0;
start = clock();
for (int i = 1; i <= N; ++i) {
random++;
}
end = clock();
double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by program is : " << fixed
<< time_taken << setprecision(5) << '\n';
return 0;
}
The ones marked Out of Syllabus were literally trillions of times the curent age of the universe. So, I hope it's okay not to calculate them xD
Conclusion
This article (especially the table above) can be used as a reference for you to decide, based on the time limit and the constraints what time complexity you should target to get that green tick - ✅