Electronic Design Automation

4.2.1. Asymptotic notations

In computational complexity theory, not all parts of an algorithm's running time are essential. In fact, only the rate of growth or the order of growth of the running time is typically of most concern in comparing the complexities of different algorithms. For example, consider two algorithms A and B, where A has longer running time for smaller input sizes, and B has a higher rate of growth of running time as the input size increases. Obviously, the running time of B will outnumber that of A for input sizes greater than a certain number. As in real applications, the input size of a problem is typically very large, algorithm B will always run more slowly, and thus we will consider it as the one with higher computational ...