I have always asked myself this, especially about x4 or x8 anti-aliasing. It seems that over the years, the algorithm has remained the same but needs more power than before due to improved game graphics.
Most disturbingly, some games look the same at x4 and x8, but perform worse at x8!
What makes anti-aliasing algorithms so computationally demanding?
It all comes down to memory bandwidth with proper anti-aliasing techniques (e.g. MSAA, SSAA, CSAA). While 8x SSAA and 8x MSAA have identical storage requirements (8x), the workload between the two algorithms is quite different. Multisample anti-aliasing adds some intelligence to the rasterization stage to reduce the number of fragments that have to be shaded, thus reducing the computational expense of anti-aliasing. However, the covered samples generated during rasterization still have to be written and averaged and this eats through a tremendous amount of memory bandwidth.
Newer image processing techniques (e.g. FXAA, MLAA) approach the problem from an entirely different perspective. They do not seek to solve the fundamental problem that leads to aliasing in the first place (inadequate sample frequency), instead they keep initial rendering as simple as possible and "fix it in post" using a complicated shader. Given the trend in hardware to increase compute power quicker than memory bandwidth and advances in display resolution, these compute-intensive approaches definitely have sticking power. Nevertheless, I have a hard time calling them anti-aliasing, as all they really do is mask aliasing after the fact.
If you are speaking of an anti-aliasing approach whose quality is measured in terms of sample rate, then the algorithm is of the memory hungry variety first discussed. The newer shader-based techniques have a myriad of implementation-specific properties that you can tune, and this is why a game that uses something like FXAA will sometimes offer vague "Low", "Medium", "High", etc. quality settings but nothing quantitative.
I know that MSAA renders the scene at a higher resolution and then downsamples it to make nice pixels. Simply, the graphics card is trying to render double or quadruple the screen resolution, and calculating more pixels is just slower. You can find more info at http://en.wikipedia.org/wiki/Multisample_anti-aliasing
TXAA though, combines MSAA with some past-frame blending, which means you don't get the flicker that MSAA sometimes gets on very thin architecture. It seems to be nvidia specific though.
Well in XNA it samples the scene for pixel data a number of times and uses the data to interpolate the colour around the lines. So it is quite demanding on the GPU to do each frame, but there are newer types of AA(MSAA, TXAA etc) which are more efficient but i am unsure how they work.
Edit: Tordin pointed out my original answer was incorrect
http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm simply because anti-aliasing algorithm have high cost
