時間複雜度

-Compile time :
-Execution time

     -Program step:       
   
        Definition : a program step is a syntactically meaningful program step whose execution time is independent of the instance characteristics,which means that something like the header of a sub program, a declaration of a variable (without assignment) is not consider as program step.
        Cautious : the execution time of program steps may be different,which depends on the degree of complexity.
   
    -How to ?
        -by a global variable (count) to calculate step by step.
        -by a table on counting the product of s/e(step/execution) and frequency (Fig.1.3)
       
    -So whats the different between two methods?
        -a global variable returns a number,
        -a table presents a function of time and step. e.g. 2n+n , n is a scale of input.
   
    -The best / average / worst step count.

---

-The big O notation:
    -Definition :   
    f(n) = O(g(n)) iff there exist positive constants c and n0 such that f(n) <= cg(n) for all n,n>=n0

-The omega notation:
    -Definition :
    f(n) = omega(g(n)) iff there exist positive constants c and n0 such that f(n) >= cg(n) for all n,n>=n0

-The theta notation:
    -Definition :
    f(n) = theta(g(n)) iff there exist positive constants c1,c2 and n0 such that c1g(n0) <=f(n)<=c2g(n) for all n,n>=n0.

-結論：
    1.Ｏ考慮的是函數上限(Upper bound)，omega則考慮下限，theta則是Ｏ跟omega的夾擠
    2.取的都是最函數趨勢影響最重要的一項