Time complexity of a loop with few operations

Question

It is known that a while-loop(Ex: while(n--)) or a for-loop(Ex: for(i=0; i<n; i++))'s time of execution depends on the variable n, i.e. O(n). Also, on an online judge, 10^7 operations ≈ 1s. But I tried executing a while-loop and a for-loop for n > 10^9 with few operations and it seems to run easily under 1 sec. I am curious why this is happening?

#include <iostream>
using namespace std;
#define ll long long 
int main(){
    ll t = 1e18;
    ll cnt = 0;
    while(t--){
        cnt++;
    }
    cout << cnt << '\n';
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Output: 1000000000000000000
Time elapsed: 0.003174 s.

The time complexity does not change and remains O(n). But the CPU may cache the instructions and so will execute them "bloody fast". Or the compiler has optimized the entire loop away and just assigned cnt= 1e18; — Paul Ogilvie
Condition 10^7 operations ≈ 1s is never static and differs on different platforms — thisisjaymehta

463035818_is_not_a_number 463035818_is_not_a_number · Accepted Answer · 2020-06-23T11:14:27

The code you write is not instructions for your cpu, but instructions for your compiler to generate instructions for your cpu. In this specific case it is rather simple to see that this

long long  t = 1e18;
long long cnt = 0;
while(t--){
    cnt++;
}
cout << cnt << '\n';

can be replaced by

long long cnt = 1e18;
cout << cnt << '\n';

without altering the observable behavior of the program.

Time complexity of a loop with few operations

3 Answers