Asymptotic notations

Introduction to Asymptotic notations for
Discrete mathematical structure
Algorithms

1. Growth of function & Asymptotic Notations By Mamata Pandey

2. Growth of function Given a function f(n) f(n) grows as value of n increases function f(n) it is required to estimate growth rate that is valid for all n >=n o where n o is some constant value

3. Asymptote Asymptote is a line or curve represented by a function say g(n) that approaches a given curve say f(n) but never reaches as they tend to infinity We can say f(n) grows like g(n) i.e. growth of function is considered like g(n) It is said that f(n) is asymptotically bound by g(n)

4. What are Asymptotic Notations For a given function f(n) asymptotic notations Asymptotic notations are used estimate or to bound the growth of f(n) in terms of other simpler function g(n) like n, n 2 , log(n) etc. They provide approximate but meaningful assumptions about complexity of f(n)

5. Asymptotic Notations Big Oh notation Big Omega notation Big Theta notation Little oh notation Little omega notation

6. Big Oh (O) Notation It provides upper bound for f(n) The function f(n) = O(g(n) iff there exist positive constants c and n o such that 0<= f(n) <= cg(n) for all n>= n o

7. Big Omega ( Ω )Notation It provides lower bound for f(n) The function f(n) = Ω (g(n) iff there exist positive constants c and n o such that 0<=cg(n)<= f(n) for all n>= n o

8. Theta( )Notation It provides tight bound for f(n) The function f(n) = (g(n) iff there exist positive constants c1 and c2, and n o such that c1g(n)<= f(n) <= c2g(n) for all n>= n o ~ ~

9. Little oh (o) Notation Little o-notation to denote an upper bound that is not asymptotically tight. The function f(n) = o(g(n)) iff there exist positive constants c and n o such that 0<= f(n) < cg(n) for all n>= n o in o-notation, the function f (n) becomes insignificant relative to g(n) as n approaches infinity; that is,

10. Little omega ( w ) Notation w –notation is used to denote a lower bound that is not asymptotically tight The function f(n) = w (g(n)) iff there exist positive constants c and n o such that0<=cg(n)< f(n) for all n>= n o The relation implies that f(n) becomes arbitrarily large relative to g(n)as n approaches infinity. That is,

11. Example: f(n)= 7n 3 -3n 2 +5n+12 or, f(n) ≤ |7n 3 |+|-3n 2 |+|5n|+|12| or, f(n) ≤ 7n 3 +3n 3 +5n 3 +12n 3 or, f(n) ≤ 27n 3 or, f(n)=O(n 3 ) where c=27 and n o =0

12. Example f(n)= 7n 3 -3n 2 +5n+12 or, f(n) ≥ 7n 3 or, f(n) = Ω (n 3 ) where c=7 and n o =0 Now, 7n 3 ≤ f(n) ≤ 27n 3 or, f(n) = (n 3 ) where c1=7 ,c2=27 and n o =0 ~

13. Example: Let f(n)= (n 3 ), Here n 3 provides tight bound hence f(n)=O(n 3 ) and f(n)= Ω (n 3 ), then f(n) ≥ c n 3 ≥ c n 2 ≥ cn ≥ c and f(n) ≤ c’ n 3 ≤ c’n 4 ≤ c’n 5 … ≤ c’n m where c, c’ c1, c2 , c3 are constants and m>=3 ~

14. But n 2 , n and c provide lower bound which is not tight hence f(n) = w (n 2 )= w (n)= w (c) Simillarly n 4 , n 5 or any higher power of n p rovides lower bound that is not asymptotically tight. f(n) = o (n 4 )= o (n 5 )= ……= o (n m )

15. Application of asymptotic notations Calculating and comparing time complexities of algorithms f(n) is a function representing number of operations for a problem of size n