Asymptotic notation

Big Oh Notation, Big Omega Notation, Big Theta Notation

1. Asymptotic Notations

2. Introduction In mathematics, computer science, and related fields,  big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. The  time complexity  of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. When it is expressed using big O notation, the time complexity is said to be described  asymptotically , i.e., as the input size goes to infinity.

3. Asymptotic Complexity Running time of an algorithm as a function of input size n for large n . Expressed using only the highest-order term in the expression for the exact running time. Instead of exact running time, say Q ( n 2 ). Describes behavior of function in the limit. Written using Asymptotic Notation . The notations describe different rate-of-growth relations between the defining function and the defined set of functions.

4. Big O -notation O ( g ( n )) = { f ( n ) :  positive constants c and n 0, such that  n  n , we have f ( n )  c g ( n ) } For function g ( n ), we define O ( g ( n )), big-O of n , as the set: g ( n ) is an asymptotic upper bound for f ( n ). Example: f(n)=3n+2 and g(n)=n Prove f ( n )  c g ( n ) f(n)=100n+5 and g(n)=n 2 Prove f ( n )  c g ( n )

5. f(n)=n^2 g(n)=2^n Big O Notation

6.  -notation g ( n ) is an asymptotic lower bound for f ( n ). Example: f(n)=3n+2 and g(n)=n Prove f ( n ) >= c g ( n ) f(n )=n 3 and g(n)=n 2 Prove f ( n ) >= c g ( n )  ( g ( n )) = { f ( n ) :  positive constants c and n 0, such that  n  n , we have c g ( n )  f ( n ) or f(n)>=cg(n) } For function g ( n ), we define  ( g ( n )), big-Omega of n , as the set:

7. Big Omega Notation

8. -notation  ( g ( n )) = { f ( n ) :  positive constants c 1 , c 2 , and n 0, such that  n  n , we have c 1 g ( n )  f ( n )  c 2 g ( n ) } For function g ( n ), we define  ( g ( n )), big-Theta of n , as the set: g ( n ) is an asymptotically tight bound for f ( n ). Example: f(n)=3n+2 and g(n)=n Prove

9. Relations Between Q , O, W

10. Basic Asymptotic Efficiency classes C constant, we write O(1) logN logarithmic log 2 N log-squared N linear NlogN   N 2 quadratic N 3 cubic 2 N exponential N! factorial

11. Properties of Asymptotic Notation 1. Transitive If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n)) If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)) If f(n) = Ω(g(n)) and g(n) = Ω(h(n)), then f(n) = Ω(h(n)) 2. Reflexivity f(n) = Θ(f(n)) f(n) = O(f(n)) f(n) = Ω(f(n )) 3. Symmetry f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n )) 4. Transpose Symmetry f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

12. The End