In most cases using list/dict comprehensions gives a noticeable performance boost when timing the code, but does it affect the asymptotic complexity of the algorithm?
As I understand, the difference is due to the way comprehensions are evaluated compared to explicit cycles, but this difference should be a constant factor and in that case asymptotic complexity doesn't change and then with the increase in the size of the problem, there should eventually come a point when both versions should perform at the same speed. Is my thinking correct?
At the same time, when I tried to test it, comprehensions have been outperforming explicit cycles all the way until I got to sizes where I as running out of memory.
Great question, but that's not how asymptotic complexity works. It's not that they will converge to the same amount of time, it's that they would both grow in the same way. For instance, algorithms that take 2*n and n are of the same asymptotic complexity, but the former will always take two times as long. I can't see any reason why the comprehensions would not have the same complexity, but you can test this empirically with timing tests.