Asymptotic Notations

Asymptotic Notations:
Two important reasons to determine the operation and step-counts are (1) to compare the time complexities of two programs that solved the same problem and (2) to predict the growth in run time as the instance characteristics change. When using step count method, we account all operations. However, this method is itself inexact. Both the instructions x=y and x = y + z + (x / y) count as one step. Because of inexactness of what a step stands for. The exact step count isn t very useful for comparative purposes.
With previous discussion as motivation, we introduce a notation that will enable us to make meaningful (though inexact) statements about the time and space complexities of program, this notation is called Asymptotic Notations, and it describes the behavior of the time or space complexity for large instance characteristics.
1. Big Oh Notation(O):
The Big Oh notation provides an upper bound for the function f.
Definition: f(n) = O(g(n)) iff ( if and only if) positive constants c and n0 exist such that f(n) ? c g(n) for all n , n ? n0.
Theory: if there is an equation f(n)= amnm + am-1nm-1 +….+ a1n + a0
the function degree is m, then f(n)= O(nm).
Ex: [Linear function]: consider f(n) = 3n + 2 = O(n)
That 3n + 2 ? 4n for all n ? 2.
Ex: [Quadratic function]: consider f(n) = 10n2+4n +2=O(n2)
That 10n2+4n +2 ? 11n2 for all n ? 5.
Ex: [Exponential function]: consider f(n) = 6* 2n+n2= O(2n)
That 6*2n + n2 ?7 * 2n for all n ? 4.
Ex: [Constant function]: consider f(n) =9= O(1).
That 9 ? 9*1 , setting c=9 and n0=1 satisfies the definition of Big Oh.

Note: n0 ? 0 and must be positive.
2. Omega Notation (?):
The Omega Notation described as the lower bound of the function f, permits us to bound the value of f from below.
Definition: f(n) =?(g(n)) iff (if and only if) positive constants c and n0 exist such that f(n) ? c g(n) for all n , n ? n0.
Theory: if there is an equation f(n)= amnm + am-1nm-1 +….+ a1n + a0
the function degree is m, then f(n)= ?(nm).
Ex: [Linear function]: consider f(n)= 3n+2= ?(n)
That 3n+2? 3n for all n ? 1.
Ex: [Quadratic function]: consider f(n) =10n2+4n +2= ?(n2)
That 10n2+4n +2? 10 n2 for all n ?1.
Ex: [Exponential function]: consider f(n) = 6* 2n +n2= ?(2n)
That 6*2n + n2 ? 6 * 2n for all n ? 1.
Ex: [Constant function]: consider f(n) =9= ?(1).
That 9?9*1, setting c=9 and n0=1 satisfies the definition of Omega.
3. Theta Notation (?):