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
– Paul Ogilvie, Commented Jun 23, 2020 at 11:15
Condition 10^7 operations ≈ 1s is never static and differs on different platforms — thisisjaymehta
– thisisjaymehta, Commented Jun 23, 2020 at 12:16

463035818_is_not_an_ai · Accepted Answer · 2020-06-23 11:14:27Z

3

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.

answered Jun 23, 2020 at 11:14

463035818_is_not_an_ai

128k11 gold badges115 silver badges240 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Abhishekk Over a year ago

What other operations are not dependent on the loop?

463035818_is_not_an_ai Over a year ago

@AbhishekKumar sorry, i dont understand your question. In your code nothing depends on the loop because all it does is cnt = 1e18; and t = 0; but you are not using t after the loop so it doesnt matter whether the loops decrements it or not

xkcdjerry · Accepted Answer · 2021-08-01 07:46:01Z

TL;DR : The compiler simply discarded your loop , cleared t and stuck 1e18 into cnt. If you want to know how I came to this conclusion,read on:

On my computer and g++ -O1/-O0 the program took litraly forever to run but using -O2 it finished instantly (the same as the asker's situation), so I will use the -S -O2 assembly code:

leaq    _ZSt4cout(%rip), %rdi
    movabsq $1000000000000000000, %rsi
    movq    %fs:40, %rax
    movq    %rax, 8(%rsp)
    xorl    %eax, %eax
    call    _ZNSo9_M_insertIxEERSoT_@PLT
    leaq    7(%rsp), %rsi
    movl    $1, %edx
    movb    $10, 7(%rsp)
    movq    %rax, %rdi
    call    _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l@PLT

Clearly the compiler just stuck 1e18 into cnt (movabsq XXX %rsi), set t to 0 (using the magic of xorl %eax %eax to clear %eax) then skipped the loop (there was no jmp or je or similar commands,and proceeded to cout (via call _XXX_insert_XXX and later _ostream_insertXXX)

ak_linus · Accepted Answer · 2020-06-23 19:52:56Z

-2

The time complexity for a simple loop (doesn't really matter which type) is O(n), that's clear.

But you should know that CPU's store some information in its fast access cache that is frequently used. However, the compiler optimizes the code by identifying which instructions (code) can be altered to produce lesser instructions while retaining the logic. While compiler optimization is a huge topic, loops are a prime target since they repeat the same set of instructions over and over.

And let's just consider the fact that a modern CPU executing a highly optimized set of compiled instructions at ~3 billion ops/sec will blaze through the instructions in microseconds.

edited Jun 23, 2020 at 19:52

answered Jun 23, 2020 at 11:39

ak_linus

5624 silver badges6 bronze badges

2 Comments

Paul Ogilvie Over a year ago

I am not sure it is the compiler that does this task of optimization by identifying which instructions (code) needs caching. The compiler's instructions cannot dictate the CPU which instructions to cache. The CPU does that itself.

ak_linus Over a year ago

@PaulOgilvie , seems you are right. The CPU has it's own hardware and instructions to manage caching. I only remembered the use of TLB and and cache writing policies after reading your comment. CPU handles the cache but code optimization is done mostly by the compiler.

Collectives™ on Stack Overflow

Time complexity of a loop with few operations

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related