Wouldn't it be (O(n) + O(n) + ...) at the worst? And if it's on lazy sequences, which I thought it was, then composing a .Select and an .Aggregate should only involve a single pass through the sequence.
The problem is that it makes it so conveniently easy to do brute-force tactics that....oh the horrible things I've seen...code gets littered with LINQ doing naive queries repeatedly over massive sets of data. Of course you need good coders and good code audits, but LINQ, I think, gives a unsupported sense of comfort that one is making good code (where if people had to code these as loops, it would become very evident very early on that maybe they should rethink their approach).