Consider the following program, which is a dummy code I wrote to get a better grasp of how time complexities actually work. The interesting thing I found is that if try to run the same code in Codechef’s IDE you’ll notice that it exceeds the time limit of 1 sec where as if you try running the same code by commenting out the 2nd statement of nested loop ( one where we are pushing elements into arr vector) you’ll notice a drastic difference in time taken in this case.
We know that push_back operation takes O(1) and in both the cases I mentioned above overall time complexity of the program will be O(n^2) then What could the reason of such drastic change in time taken by the program if the time complexity is same?
#include <iostream>
#include<vector>
using namespace std;
int main() {
long long n=1e4, sum=0;
vector<long long> arr;
for(long long i=0;i<n;i++)
{
for(long long j=0;j<n;j++)
{
sum+=j;
arr.push_back(j);
}
}
cout<<sum;
return 0;
}