Asymptotic Analysis

1. English notation of Big-Oh:

    Let T(n) the worst-case running time of an algorithm, n= 1, 2, 3, ......

    T(n) = O(f(n)) if enventually (for sufficiently large n ), T(n) is bounded above by a constant multiple of f(n)

 

2. Formal definition of Big-Oh:

    T(n) = O(f(n)) iif there exist contants c, n0 > 0 , such that:

    T(n) <= c f(n) , for all n >= n0

 

3. Formal definition of Omega Notation:

    T(n) = Ω(f(n)) iif there exist contants c, n0 > 0 , such that:

    T(n) >= c f(n), for all n >= n0

 

4. Formal definition of Theta Notation:

    T(n) = Θ(f(n)) iif there exist contants c1,c2, n0 > 0 , such that:    c2 f(n) >= T(n) >= c1 f(n), for all n >= n0

 

5. Formal definition of Little-Oh Notation:

    T(n) = o(f(n)) iif for all c >0 , there exists contant n0 > 0 , such that:

    T(n) <= c f(n) , for all n >= n0