IIRC, the "energy" may affect up to 3 below pixels (left, right, center), so each pixel of a removed seam requires re-calculations downwards in the shape of a f

IIRC, the "energy" may affect up to 3 below pixels (left, right, center), so each pixel of a removed seam requires re-calculations downwards in the shape of a funnel going to the left and right with a maximum of 45°. In the worst case, this means re-calculatable pixels are in the form of a triangle with a top row pixel as its tip and a 90° angle there. So, for a landscape-oriented image of aspect ratio 2:1 that would mean re-calculating up to 50% of its pixels. For narrower ones, that percentage is even higher, so not too much to gain.