一、Asymptotic analysis
Suppose we are considering two algorithms, A and B, for solving a given problem. Furthermore, let us say that we have done a careful analysis of the running times of each of the algorithms and determined them to be and , respectively, where n is a measure of the problem size. Then it should be a fairly simple matter to compare the two functions and to determine which algorithm is the best!
这段话的意识，比较两种算法的时间成本来判定哪种算法更好。但实际应用中，T(n)是随着问题的规模n变化的，在事先不知道n的情况下，没法比较两种算法的优劣。由此，引入“Asymptotic behavior”，比较两种算法的T(n)在n比较大时的“增长级数”，例如：对数增长、线性增长、指数级增长。
二、Big Oh notation
In 1892, P. Bachmann invented a notation for characterizing the asymptotic behavior of functions. His invention has come to be known as big oh notation:
Definition (Big Oh) Consider a function f( n) which is non-negative for all integers . We say that `` f( n) is big oh g( n),'' which we write f( n)= O( g( n)), if there exists an integer