I am looking for an example where an algorithm is apparently changing its complexity class due to compiler and/or processor optimization strategies.
Change of the complexity class through compiler optimization?
c++;algorithms;optimization;big o
Lets take a simple program which prints the square of a number entered on the command line.#include <stdio.h>int main(int argc, char **argv) {    int num = atoi(argv[1]);    printf(%d\n,num);    int i = 0;    int total = 0;    for(i = 0; i < num; i++) {        total += num;    }    printf(%d\n,total);    return 0;}As you can see, this is a O(n) calculation, looping over and over again.Compiling this with gcc -S one gets a segment that is:LBB1_1:        movl    -36(%rbp), %eax        movl    -28(%rbp), %ecx        addl    %ecx, %eax        movl    %eax, -36(%rbp)        movl    -32(%rbp), %eax        addl    $1, %eax        movl    %eax, -32(%rbp)LBB1_2:        movl    -32(%rbp), %eax        movl    -28(%rbp), %ecx        cmpl    %ecx, %eax        jl      LBB1_1In this you can see the add being done, a compare and a jump back for the loop.Doing the compile with gcc -S -O3 to get optimizations the segment between the calls to printf:        callq   _printf        testl   %ebx, %ebx        jg      LBB1_2        xorl    %ebx, %ebx        jmp     LBB1_3LBB1_2:        imull   %ebx, %ebxLBB1_3:        movl    %ebx, %esi        leaq    L_.str(%rip), %rdi        xorb    %al, %al        callq   _printfOne can now see instead it has no loop and furthermore, no adds.  Instead there is a call to imull which multiplies the number by itself.The compiler has recognized a the loop and the math operator inside and replaced it by the proper calculation.Note that this included a call to atoi to get the number.  When the number exists already in the code, the complier will pre-calculate the value rather than making actual calls as demonstrated in a comparison between the performance of sqrt in C# and C where sqrt(2) (a constant) was being summed across a loop 1,000,000 times.