There was a significant increase in research in algorithms and complexity, including the establishment of several new centres of excellence. This increased activity was not, however, limited to the research groups specialising in this area, but permeated research in many other areas, such as data-mining, vision, evolutionary computing, agents, etc.
This was noted as a result of the 2001 International Review of UK Research in Computer Science, which (rightly) pointed out that algorithms and complexity, at the time, was under-represented here. But, the most encouraging aspect of the above observation is the bit about algorithmic analysis gaining recognition for its importance, outside of its own community.
Another paragraph noted what might be regarded as a more general trend, namely that the research being assessed was generally more rigorous than the previous RAE (2001), i.e. more mathematical analysis, and more careful and detailed experiments.