Asymptotic notation

Asymptotic Notation helps to represent time like worst case ,best case and average case

1. Data Structure and Algorithms-Searching Techniques Prepared By, S.Sajini AP/CSE

2. MATHEMATICAL NOTATIONS, ASYMPTOTIC NOTATION - BIG O , OMEGA, THETA MATHEMATICAL FUNCTIONS

3. 1. FLOOR AND CEILING FUNCTIONS: Floor Function: the greatest integer that is less than or equal to x Ceiling Function: the least integer that is greater than or equal to x Notation

4. 2. Remainder function : Modular arithmetic Let x be any integer and let M be a positive integer. Then x ( mod M) Eg: 13 (mod 5) =3 3. Integer and Absolute Value functions INT (x) converts x into an integer by deleting the fractional part of the number ABS (x) or |x| gives the greater of x or -x Eg: INT(3.14) =3 |15| = 15 |-0.33| = 0.33

5. 4. Summation Symbol: sums Summation symbol : Σ This symbol (called  Sigma ) means "sum up" 5. Factorial Function The  factorial function  (symbol:  ! ) says to  multiply all whole numbers  from our chosen number down to 1. n! = 1.2.3…. (n-2).(n-1) E.g: 2! = 1.2 = 2

6. 6. Permutations A permutation of a set of n elements is an arrangement of the elements in a given order . E.g: Permutations of the elements a, b and c arbe abc, acb, bac, bca, cab, cba 7 . Exponents and Logarithms Exponents are also called Powers or Indices. Example:  5 3  = 5 × 5 × 5 = 125 Logarithm of any positive number x to the base b, written as log b ( x ) => y = log b ( x ) => b y = x

7. Asymptotic Notation– Big, Omega , Theta Asymptotic Notations refers to computing the running time of any operation in mathematical units of computation. Ο Notation (Big) Ω Notation (Omega) θ Notation (Theta)

8. Big Oh Notation, Ο It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete. O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= cg(n) for all n >= n0}

9. Big O Notation Big-O notation, where the "O" stands for "order of", is concerned with what happens for very large values of n. For example, if a sorting algorithm performs n 2 operations to sort just n elements, then that algorithm would be described as an O(n 2 ) algorithm. When expressing complexity using Big O notation, constant multipliers are ignored. So a O(4n) algorithm is equivalent to O(n), which is how it should be written.

10. Big O Notation If f(n) and g(n) are functions defined on positive integer number n, then f(n) = O(g(n)) That is, f of n is big O of g of n if and only if there exists positive constants c and n, such that f (n) ≤ cg(n)  This means that for large amounts of data, f(n) will grow no more than a constant factor than g(n). Hence, g provides an upper bound.

11. Ω Notation: Ω notation provides an asymptotic lower bound

12. Omega Notation Omega notation provides a tight lower bound for f(n). This means that the function can never do better than the specified value but it may do worse. Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and Ω(g(n)) = {h(n): ∃ positive constants c > 0, n such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n }. Examples of functions in Ω(n 2 ) include: n 2 , n 2.9 , n 3 + n, 540n 2 + 10 Examples of functions not in Ω(n 3 ) include: n, n 2.9 , n 2

13. Θ Notation: Θ((g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}

14. Theta Notation Theta notation provides an asymptotically tight bound for f(n). Θ notation is simply written as, f(n) ∈ Θ(g(n)), where n is the problem size and Θ(g(n)) = {h(n): ∃ positive constants c 1 , c 2 and n such that 0 ≤ c 1 g(n) ≤ h(n) ≤ c 2 g(n), ∀ n ≥ n }. Hence, we can say that Θ(g(n)) comprises a set of all the functions h(n) that are between c1g(n) and c2g(n) for all values of n ≥ n . To summarize, The best case in Θ notation is not used. Worst case Θ describes asymptotic bounds for worst case combination of input values. If we simply write Θ, it means same as worst case Θ.

15. Categories of Algorithms Constant time algorithms have running time complexity given as O(1) Linear time algorithms have running time complexity given as O(n) Logarithmic time algorithms have running time complexity given as O(log n) Polynomial time algorithms have running time complexity given as O( nk ) where k>1 Exponential time algorithms have running time complexity given as O(2 n ) n O(1) O(log n) O(n) O(n log n) O(n 2 ) O(n 3 ) 1 1 1 1 1 1 1 2 1 1 2 2 4 8 4 1 2 4 8 16 64 8 1 3 8 24 64 512 16 1 4 16 64 256 4,096