Using Accumulate for 20,000,000 size list. Time < 1 Hour
Your timings seem way too high. On my PC,
Accumulate on an 20.000.000-element packed array takes about 50ms. A For loop (not compiled!) needs about one minute for 20 million values. My PC may be fast, but not that fast. Make sure your array contains only machine-precision reals and is packed. Otherwise, any comparison with C or C++ doesn't make much sense, because values in a C++
double* array are always machine precision and "packed".
Why is Accumulate much faster than using a For loop?
For loop is written in an interpreted language, while
Accumulate is (presumably) written in a low-level language; It might even use special SIMD CPU instructions that process multiple values in a single instruction. The interpreted loop on the other hand needs more than one CPU instruction just for a single addition.
What is the exact algorithm for Accumulate?
As others said in the comments, we don't know. But the obvious algorithm (take each element from the input buffer, add it to an accumulator register, store it in the output buffer) needs n read operations, n-1 add operations and n write operations. And I don't see how you could get the right result without reading each input data, writing each output value and adding n-1 values. So my guess would be that Mathematica does something like that.
Can this algorithm be used in object-oriented languages (I am familiar with C++) to compute partial sums of an array faster than a for loop?
C++ has a library function partial_sum, and (at least in my implementation) that's exactly how it's implemented.
If yes, then how much will the performance gain (big-O notation is preferable) in C++ be compared to Mathematica?
Any decent algorithm will be O(n). Probably your For loop is O(n), too.
If the question really was: Will a C++ implementation be faster, slower or just as fast as Mathematica's Accumulate, then the answer depends mostly on how smart your C++ compiler is. My guess is that any modern CPU can add numbers much faster than it can read/write them from and to main memory. So performance depends on things like whether the C++ compiler is smart enough to make the CPU prefetch values from main memory to cache before it needs them. If it is, and if Mathematica's implementation does the same, they might just be equally fast.