vikram_sp <vikramforum@xxxxxxxxx> writes: > I am wondering what may be the COMPLEXITY of GCC compiler in big Oh > notation or other notation. > I have some intuition that lexical analyzer's complexity is O(n) and that of > parser is O(n^3). Optimization is NPC. Code generator might have some > log(n) factor. > Taking these things in accounts what is the time complexity of compilers > in general and GCC in particular. > Likewise space complexity may also be given thought? Most of the compiler is linear in the size of the input. Some specific optimization passes have a larger complexity. Some optimization passes are linear in the number of basic blocks or in the number of pseudo-registers. Register allocation is O(n^2) in the number of pseudo-registers. Ian
