Asymptotic Notation

PPT on asymptotic notation in Algorithm

1. Asymptotic Notation

2. Analysis of Algorithms What is the goal of analysis of algorithms ? To compare algorithms mainly in terms of running time but also in terms of other factors (e.g., memory requirements, programmer's effort etc.) What do we mean by running time analysis ? Determine how running time increases as the size of the problem increases. An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.

3. Types of Analysis Worst case Provides an upper bound on running time An absolute guarantee that the algorithm would not run longer, no matter what the inputs are Best case Provides a lower bound on running time Input is the one for which the algorithm runs the fastest Average case Provides a prediction about the running time Assumes that the input is random

4. Asymptotic Analysis To compare two algorithms with running times f(n) and g(n), we need a rough measure that characterizes how fast each function grows. Express running time as a function of the input size n (i.e ., f(n) ) . Compare different functions corresponding to running times. Such an analysis is independent of machine time, programming style,etc . Compare functions in the limit, that is, asymptotically! (i.e., for large values of n )

5. Asymptotic Notation A way to describe the behavior of functions in the limit or without bounds . The notations are defined in terms of functions whose domains are the set of natural numbers N={0,1,2,...} . Such notations are convenient for describing the worst-case running time function T(n) . It can also be extended to the domain of real numbers.

6. Example : - x is asymptotic with x + 1 limit - Roughly translated might read as: x approaches ∞, f(x) approaches k for x close to ∞, f(x) is close to k Two limits often used in analysis are: = 1/x = 0 = cx = ∞ for c>0   Asymptotic Notation

7. Outline   lliil Asymptotic growth rate : -

8. possibly asymptotically tight upper bound for f(n) - Cannot do worse, can do better n is the problem size. f(n) ∈ O(g(n)) where: Meaning for all values of n ≥ (n ) is on or below g(n). O(g(n)) is a set of all the functions f(n ) that are less than or equal to cg(n), ∀ n ≥ .   Big-O Notation (Omicron) O(g(n)) = { f(n ): ∃ positive constants c, such that 0 ≤ f(n ) ≤ c g(n), ∀ n ≥ }   If f(n) ≤ cg(n), c > 0, ∀ n ≥ then f(n) ∈ O(g(n))  

9. Example of Big O notation   Solution :- 0 ≤ 2 ≤ c 0/ ≤ 2 / ≤ c / Determine C ≤ 2/n ≤ c ≤ 2/1 ≤ c = 2   Substitute Divide by   = 0 2/n maximum when n=1 Satisfied by c=2   1000 + 50n = O( ) with c=1050 and = 1   Satisfied by = 1 ∀ n ≥ =1   If f(n) ≤ cg(n), c > 0, ∀ n ≥ then f(n) ∈ O(g(n))   Determine 0 ≤ 2/ ≤ 2 0 ≤ 2/2 ≤ 0 ≤ 1 ≤ = 1 0 ≤ 2 ≤ 2  

10. Big Omega Notation ( Ω ) possibly asymptotically tight lower bound for f(n) - Cannot do better, can do worse f(n) ∈ Ω(g(n)) where: Meaning for all values of n ≥ (n ) is on or above g(n). Ω(g(n)) is a set of all the functions f(n ) that are greater than or equal cg(n), ∀ n ≥ .   Ω(g(n)) = {f(n ): ∃ positive constants c > 0, such that 0 ≤ cg(n) ≤ f(n ), ∀ n ≥ }   If cg(n) ≤ f(n), c > 0 and ∀ n ≥ , then f(n) ∈ Ω(g(n))  

11. Example of Ω notation Solution :- ≤ cg(n) ≤ f(n) 0 ≤ c ≤ 3 + n 0/ ≤ c / ≤ 3 / + n/ 0 ≤ c ≤ 3 + 1/n 0 ≤ c ≤ 3 0 ≤ 3 ≤ 3 + 1/ -3 ≤ 3-3 ≤ 3-3 + 1/ -3 ≤ 0 ≤ 1/   = 1 satisfies   c = 3   that 3 + n = Ω( )   3 + n = Ω ( ) with c=1 and = 1  

12. Big Theta Notation(  ) asymptotically tight bound for f(n) f(n) ∈  ( g(n)) where : Positive means greater than 0.  (g(n )) is a set of all the functions f(n ) that are between g(n ) and g(n ), ∀ n ≥ . If f(n) is between g(n ) and g(n ), ∀ n ≥ , then f(n) ∈  ( g(n))    ( g(n)) = {f(n ): ∃ positive constants , , such that 0 ≤ g(n ) ≤ f(n ) ≤ g(n ), ∀ n ≥ }  

13. Example of  notation Θ: ½ - 3n ∈ Θ( ) when = 1/14, = ½ and = 7   Divide by   n2 ≤ ½ - 3n ≤ ≤ ½ - 3/n ≤ O: Determine = ½ ½ - 3/n ≤ as n → ∞, 3/n → 0 = ½ therefore ½ ≤ o r = ½ maximum for as n → ∞ Ω : Determine = 1/14 0 < ≤ ½ - 3/n - 3/n > 0 minimum for = 7 0 < = ½ - 3/7 = 7/14 - 6/14 = 1/14 : Determine = 7 ≤ ½ - 3/ ≤ 1/14 ≤ ½ - 3/ ≤ ½ -6/14 ≤ -3/ ≤ 0 - ≤ -3*14/6 ≤ 0 ≥ 42/6 ≥ 0 ≥ 7   Solution :- Show that ½ - 3n ∈ Θ( ) Determine ∃ , , positive constants such that:  

14. Relations Between Q , W , O Theorem : For any two functions g ( n ) and f ( n ), f ( n ) =  ( g ( n )) iff f ( n ) = O ( g ( n )) and f ( n ) =  ( g ( n )) . I.e.,  ( g ( n )) = O ( g ( n )) Ç W W ( g ( n )) In practice, asymptotically tight bounds are obtained from asymptotic upper and lower bounds.

15. Little-o Notation ( o micron ) non-asymptotically tight upper bound for f(n) f(n) ∈ o(g(n)) where : f(n) / g(n) = 0 for any 0 < c < ∞   o(g(n)) = {f(n ): for any constant c > 0, ∃ a constant > 0, such that: 0 ≤ f(n ) < cg(n), ∀ n ≥ }   o(g(n)) = {f(n ): for any constant c > 0, ∃ a constant > 0, such that: 0 ≤ f(n ) < cg(n), ∀ n ≥ }         o ( f ( n )) f ( n ) n

16. Little- ω Notation (omega) non-asymptotically tight lower bound for f(n) f(n) ∈ ω(g(n)) where : for any 0 < c ≤ ∞ f(n ) / g(n) = c for some 0 < c ≤ ∞ Ω possibly asymptotically tight lower bound ω non-asymptotically tight lower bound   ω(g(n)) = {f(n ): for any constant c > 0, ∃ a constant > 0, such that 0 ≤ cg(n) < f (n ), ∀ n ≥ }   Ω(g(n)) = {f(n ): for some constant c > 0, ∃ a constant > 0, such that 0 ≤ cg(n) ≤ f (n), ∀ n ≥ }   f(n ) / g(n) = ∞    ( f ( n )) f ( n ) n

17. Comparison of Functions An imprecise analogy between the asymptotic comparison of two function f and g and the relation between their values: f(n) = O(g(n)) ≈ f(n ) ≤ g(n) f(n ) = Ω(g(n)) ≈ f(n ) ≥ g(n) f(n ) = Θ(g(n )) ≈ f(n) = g(n) f(n) = o(g(n)) ≈ f(n ) < g(n) f(n ) = ω(g(n)) ≈ f(n) > g(n)

18. lim [ f ( n ) / g ( n )] = Þ f ( n ) Î o ( g ( n )) n  lim [ f ( n ) / g ( n )] <  Þ f ( n ) Î O ( g ( n )) n  0 < lim [ f ( n ) / g ( n )] <  Þ f ( n ) Î Q ( g ( n )) n  0 < lim [ f ( n ) / g ( n )] Þ f ( n ) Î W ( g ( n )) n  Lim [ f ( n ) / g ( n )] =  Þ f ( n ) Î w ( g ( n )) n  lim [ f ( n ) / g ( n )] undefined Þ can’t say n  Limits

19. Properties Transitivity f ( n ) =  ( g ( n )) & g ( n ) =  ( h ( n ))  f ( n ) =  ( h ( n )) f ( n ) = O ( g ( n )) & g ( n ) = O ( h ( n ))  f ( n ) = O ( h ( n )) f ( n ) =  ( g ( n )) & g ( n ) =  ( h ( n ))  f ( n ) =  ( h ( n )) f ( n ) = o ( g ( n )) & g ( n ) = o ( h ( n ))  f ( n ) = o ( h ( n )) f ( n ) = w ( g ( n )) & g ( n ) = w ( h ( n ))  f ( n ) = w ( h ( n )) Reflexivity f ( n ) =  ( f ( n )) f ( n ) = O ( f ( n )) f ( n ) =  ( f ( n )) Symmetry f ( n ) =  ( g ( n )) iff g ( n ) =  ( f ( n )) Complementarity f ( n ) = O ( g ( n )) iff g ( n ) =  ( f ( n )) f ( n ) = o ( g ( n )) iff g ( n ) = w (( f ( n ))

20. Asymptotic notation in equations and inequalities On the right-hand side :-  (n 2 ) stands for some anonymous function in  (n 2 ) 2n 2 + 3n + 1 = 2n 2 +  (n) means: There exists a function f(n)   (n) such that 2n 2 + 3n + 1 = 2n 2 + f(n ) On the left-hand side :- 2n 2 +  (n) =  (n 2 ) means : No matter how the anonymous function is chosen on the left-hand side, there is a way to choose the anonymous function on the right-hand side to make the equation valid.

21. Basic Asymptotic Efficiency Classes

22. Acknowledgement Firstly , I would like to thanks Mr. Abhishek Mukhopadhyay for giving us such an interesting topic to work with and Of course last but not the least I express my esteemed gratitude to my group members Meraj,Papiya,Nazaan,Protap who put up with me during the whole period and provided me valuable guidance in times of need and gave wonderful cooperation and support to complete the project.