Function

Definitions on Function A function is something that associates each element of a set with an element of another set (which may or may not be the same as the first set). The concept of function appears quite often even in non-technical contexts. For example, a social security number uniquely identifies the person, the income tax rate varies depending on the income, and the final letter grade for a course is often determined by test and exam scores, homeworks and projects, and so on. In all these cases to each member of a set (social security number, income, tuple of test and exam scores, homeworks and projects) some member of another set (person, tax rate, letter grade, respectively) is assigned. As you might have noticed, a function is quite like a relation. In fact, formally, we define a function as a special type of binary relation. Definition (function): A function, denote it by f, from a set A to a set B is a relation from A to B that satisfies 1. for each element a in A, there is an element b in B such that <a, b> is in the relation, and 2. if <a, b> and <a, c> are in the relation, then b = c . The set A in the above definition is called the domain of the function and B its codomain. Thus, f is a function if it covers the domain (maps every element of the domain) and it is single valued. The relation given by f between a and b represented by the ordered pair <a, b> is denoted as f(a) = b , and b is called the image of a under f . The set of images of the elements of a set S under a function f is called the image of the set S under f, and is denoted by f(S) , that is, f(S) = { f(a) | a ∈ S }, where S is a subset of the domain A of f . The image of the domain under f is called the range of f. Example: Let f be the function from the set of natural numbers N to N that maps each natural number x to x2. Then the domain and co-domain of this f are N, the image of, say 3, under this function is 9, and its range is the set of squares, i.e. { 0, 1, 4, 9, 16, ....} . Definition (sum and product): Let f and g be functions from a set A to the set of real numbers R. Then the sum and the product of f and g are defined as follows: For all x, ( f + g )(x) = f(x) + g(x) , and for all x, ( f*g )(x) = f(x)*g(x) , where f(x)*g(x) is the product of two real numbers f(x) and g(x). Example: Let f(x) = 3x + 1 and g(x) = x2 . Then ( f + g )(x) = x2 + 3x + 1 , and ( f*g )(x) = 3x3 + x2 Definition (one-to-one): A function f is said to be one-to-one (injective) , if and only if whenever f(x) = f(y) , x = y . Example: The function f(x) = x2 from the set of natural numbers N to N is a one-to-one function. Note that f(x) = x2 is not one-to-one if it is from the set of integers (negative as well as non-negative) to N, because for example f(1) = f(-1) = 1 . Definition (onto): A function f from a set A to a set B is said to be onto(surjective) , if and only if for every element y of B , there is an element x in A such that f(x) = y , that is, f is onto if and only if f( A ) = B . Example: The function f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is an onto function. However, f(x) = 2x from the set of natural numbers N to N is not onto, because, for example, nothing in N can be mapped to 3 by this function. Definition (bijection): A function is called a bijection , if it is onto and one-to-one. Example: The function f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is one-to-one and onto. Thus it is a bijection. Every bijection has a function called the inverse function. These concepts are illustrated in Figure 1. In each figure below, the points on the left are in the domain and the ones on the right are in the co-domain, and arrows show < x, f(x) > relation.

Definition (inverse): Let f be a bijection from a set A to a set B. Then the function g is called the inverse function of f, and it is denoted by f -1 , if for every element y of B, g(y) = x , where f(x) = y . Note that such an x is unique for each y because f is a bijection. For example, the rightmost function in the above figure is a bijection and its inverse is obtained by reversing the direction of each arrow. Example: The inverse function of f(x) = 2x from the set of natural numbers N to the set of non-negative even numbers E is f -1(x) = 1/2 x from E to N. It is also a bijection. A function is a relation. Therefore one can also talk about composition of functions. Definition (composite function): Let g be a function from a set A to a set B, and let f be a function from B to a set C . Then the composition of functions f and g, denoted by fg, is the function from A to C that satisfies fg(x) = f( g(x) ) for all x in A . Example: Let f(x) = x2 , and g(x) = x + 1 . Then f( g(x) ) = ( x + 1 )2 .

Growth of Functions

Introduction One of the important criteria in evaluating algorithms is the time it takes to complete a job. To have a meaningful comparison of algorithms, the estimate of computation time must be independent of the programming language, compiler, and computer used; must reflect on the size of the problem being solved; and must not depend on specific instances of the problem being solved. The quantities often used for the estimate are the worst case execution time, and average execution time of an algorithm, and they are represented by the number of some key operations executed to perform the required computation. As an example for an estimate of computation time, let us consider the sequential search algorithm. Example: Algorithm for Sequential Search Algorithm SeqSearch(L, n, x) L is an array with n entries indexed 1, .., n, and x is the key to be searched for in L. Output: if x is in L , then output its index, else output 0. index := 1; while ( index ≤ n and L[ index ] ≠ x ) index := index + 1 ; if ( index > n ) , then index := 0 return index . The worst case time of this algorithm, for example, can be estimated as follows: First the key operation is comparison of keys comparing L[ index ] with x . Most search algorithms (if not all) need "comparison of keys". The largest number of execution of this comparison is n , which occurs when x is not in L or when x is at L[n] , and the while loop is executed n times. This quantity n thus obtained is used as an estimate of the worst case time of this sequential search algorithm. Note that in the while loop two comparisons and one addition are performed. Thus one could use 3n as an estimate just as well. Also note that the very first line and the last two lines are not counted in. The reasons for those are firstly that differences in implementation details such as languages, commands, compilers and machines make differences in constant factors meaningless, and secondly that for large values of n, the highest degree term in n dominates the estimate. Since we are mostly interested in the behavior of algorithms for large values of n , lower terms can be ignored compared with the highest term. The concept that is used to address these issues is something called big-oh, and that is what we are going to study here.

Big - Oh The following example gives the idea of one function growing more rapidly than another. We will use this example to introduce the concept the big-Oh. Example: f(n) = 100 n2, g(n) = n4, the following table and Figure 2 show that g(n) grows faster than f(n) when n > 10. We say f is big-Oh of g. n f(n) g(n) 10 10,000 10,000 50 250,000 6,250,000 100 1,000,000 100,000,000 150 2,250,000 506,250,000

Definition (big-oh): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be O( g(x) ) , which is read as f(x) is big-oh of g(x) , if and only if there are constants C and n0 such that | f(x) | ≤ C | g(x) | whenever x > n0 . Note that big-oh is a binary relation on a set of functions (What kinds of properties does it have ? reflexive ? symmetric ? transitive ?). The relationship between f and g can be illustrated as follows when f is big-oh of g. For example, 5 x + 10 is big-oh of x2, because 5 x + 10 < 5 x2 + 10 x2 = 15 x2 for x > 1 . Hence for C = 15 and n0 = 1 , | 5x + 10 | ≤ C | x2 | . Similarly it can be seen that 3 x2 + 2 x + 4 < 9 x2 for x > 1 . Hence 3 x2 + 2 x + 4 is O( x2 ) . In general, we have the following theorem: Theorem 1: an xn + ... + a1 x + a0 is O( xn ) for any real numbers an , ..., a0 and any nonnegative number n . Note: Let f(x) = 3 x2 + 2 x + 4, g(x) = x2, from the above illustration, we have that f(x) is O(g(x)). Also, since x2 < 3 x2 + 2 x + 4, we can also get g(x) is O(f(x)). In this case, we say these two functions are of the same order.

Growth of Combinations of Functions Big-oh has some useful properties. Some of them are listed as theorems here. Let use start with the definition of max function. Definition (max function): Let f1(x) and f2(x) be functions from a set A to a set of real numbers B. Then max( f1(x) , f2(x) ) is the function from A to B that takes as its value at each point x the larger of f1(x) and f2(x). Theorem 2: If f1(x) is O( g1(x) ) , and f2(x) is O( g2(x) ) , then (f1 + f2)( x ) is O( max( g1(x) , g2(x) ) ) . From this theorem it follows that if f1(x) and f2(x) are O( g(x) ) , then (f1 + f2)( x ) is O( g(x) ) , and (f1 + f2)( x ) is O( max( f1(x) , f2(x) ) ) . Theorem 3: If f1(x) is O( g1(x) ) , and f2(x) is O( g2(x) ) , then (f1 * f2)( x ) is O( g1(x) * g2(x) ) .

Big - Omega and Big - Theta Big-oh concerns with the "less than or equal to" relation between functions for large values of the variable. It is also possible to consider the "greater than or equal to" relation and "equal to" relation in a similar way. Big-Omega is for the former and big-theta is for the latter. Definition (big-omega): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be Ω(g(x)) , which is read as f(x) is big-omega of g(x) , if there are constants C and n0 such that | f(x) | ≥C | g(x) | whenever x > n0 . Definition (big-theta): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be θ( g(x) ) , which is read as f(x) is big-theta of g(x) , if f(x) is O( g(x) ), and Ω( g(x) ) . We also say that f(x) is of order g(x) . For example, 3x2 - 3x - 5 is Ω( x2 ) , because 3x2 - 3x - 5 ≥x2 for integers x > 2 (C = 1 , n0 = 2 ) . Hence by Theorem 1 it is θ( x2) . In general, we have the following theorem: Theorem 4: an xn + ... + a1 x + a0 is θ( xn ) for any real numbers an , ..., a0 and any nonnegative number n .

Little - Oh and Little - Omega If f(x) is O( g(x) ), but not θ( g(x) ) , then f(x) is said to be o( g(x) ) , and it is read as f(x) is little-oh of g(x) . Similarly for little-omega (ω). For example x is o(x2 ) , x2 is o(2x ) , 2x is o(x ! ) , etc.

Calculation of Big – Oh Basic knowledge of limits and derivatives of functions from calculus is necessary here. Big-oh relationships between functions can be tested using limit of function as follows: Let f(x) and g(x) be functions from a set of real numbers to a set of real numbers. Then 1. If limx→∞f(x)/g(x)=0 size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) =0} {}, then f(x) is o( g(x) ) . Note that if f(x) is o( g(x) ), then f(x) is O( g(x) ). 2. If limx→∞f(x)/g(x)=∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) = infinity } {}, then g(x) is o( f(x) ) . 3. If 0<limx→∞f(x)/g(x)<∞ size 12{0< {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) < infinity } {}, then f(x) is θ( g(x) ) . 4. If limx→∞f(x)/g(x)<∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) < infinity } {}, then f(x) is O( g(x) ) . For example, limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}(4x3 + 3x2 + 5)/(x4 – 3x3 – 5x -4) = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}( 4/x + 3/x2 + 5/x4 )/(1 - 3/x - 5/x3 - 4/x4 ) = 0 . Hence ( 4x3 + 3x2 + 5 ) is o(x4 - 3x3 - 5x - 4 ), or equivalently, (x4 - 3x3 - 5x - 4 ) is ω(4x3 + 3x2 + 5 ) . Let us see why these rules hold. Here we give a proof for 4. Others can be proven similarly. Proof: Suppose limx→∞f(x)/g(x)=C1<∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) =C rSub { size 8{1} } < infinity } {}. By the definition of limit this means that ∀ε> 0, ∃n0 such that |f(x)/g(x) – C1| < ε whenever x > n0 Hence –ε < f(x)/g(x) – C1 < ε Hence –ε +C1 < f(x)/g(x) < ε +C1 In particular f(x)/g(x) < ε +C1 Hence f(x) < (ε +C1)g(x) Let C = ε +C1 , then f(x) < Cg(x) whenever x > n0 . Since we are interested in non-negative functions f and g, this means that |f(x) | ≤C | g(x) | Hence f(x) = O( g(x) ) .

L'Hospital (L'Hôpital)'s Rule limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f(x)/g(x) is not always easy to calculate. For example take limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}x2/3x. Since both x2 and 3x go to ∞ as x goes to ∞ and there is no apparent factor common to both, the calculation of the limit is not immediate. One tool we may be able to use in such cases is L'Hospital's Rule, which is given as a theorem below.

Theorem 5 ( L'Hospital ): If limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f(x) = ∞ and limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}g(x) = ∞, and f(x) and g(x) have the first derivatives, f '(x) and g'(x) , respectively, then limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f(x)/g(x) = f '(x)/g'(x) . This also holds when limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f(x) = 0 and limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}g(x) = 0 , instead of limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f(x) = ∞ and limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}g(x) = ∞. For example, limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}x/ex = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}1/ex = 0, because (ex)' = ex, where e is the base for the natural logarithm. Similarly limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}ln x/x = ( 1/x )/1 = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}1/x = 0 . Note that this rule can be applied repeatedly as long as the conditions are satisfied. So, for example, limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}x2/ex = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}2x/ex = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}2/ex = 0.

Summary of Big – Oh Sometimes, it is very necessary to compare the order of some common used functions including the following: 1 logn n nlogn n2 2n n! nn

Now, we can use what we've learned above about the concept of big-Oh and the calculation methods to calculate the order of these functions. The result shows that each function in the above list is big-oh of the functions following them. Figure 2 displays the graphs of these functions, using a scale for the values of the functions that doubles for each successive marking on the graph. ***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***

Questions and Exercises 1. Indicate which of the following statements are correct and which are not. a. The range of a function is a subset of the co-domain. b. The cardinality of the domain of a function is not less than that of its range. c. The range of a function is the image of its domain. d. Max {f,g} is the function that takes as its value at x the larger of f(x) and g(x). 2. Indicate which of the following statements are correct and which are not. a. limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}(n2 + 3n + 5)/(4n2 + 10n + 6) = 1/4. b. 2n is big-theta of 3n. c. limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}(10n3 + 3n2 + 500n + 100)/(2n4 + 3n3) = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}(6n + 6)/(24n2 + 18n) d. limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f’/g’ = limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f’’/g’’. if f’’ and g’’ exist, and limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}f’ and limx→∞ size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {}g’ are both equal to infinity or 0. 3. Which f is not a function from R to R in the following equations, where R is the set of real numbers? Explain why they are not a function. a. f(x) = 1/x b. f(x) = y such that y 2 = x c. f(x) = x 2 – 1 4. Find the domain and range of the following functions. a. the function that assigns to each bit string (of various lengths) the number of zeros in it. b. the function that assigns the number of bits left over when a bit string (of various lengths) is split into bytes (which are blocks of 8 bits) 5. Determine whether each of the following functions from Z to Z is one-to-one, where Z is the set of integers. a. f(n) = n + 2 b. f(n) = n² + n + 1 c. f(n) = n³ - 1 6. Determine whether each of the following functions from Z to Z is onto. a. f(n) = n + 2 b. f(n) = n² + n + 1 c. f(n) = n³ - 1 7. Determine whether each of the following functions is a bijection from R to R. a. f(x) = 2x + 3 b. f(x) = x² + 2 8. Determine whether each of the following functions from R to R is O(x). a. f(x) = 10 b. f(x) = 3x + 7 c. f(x) = x² + x + 1 d. f(x) = 5ln x 9. Use the definition of big-oh to show that x4 + 5x3 + 3x2 + 4x + 6 is O(x4). 10. Show that (x² + 2x + 3) / (x + 1) is O(x). 11. Show that 5x4 + x² + 1 is O(x4/2) and x4/2 is O(5x4 + x² + 1). 12. Show that 2n is O(3n) but that 3n is not O(2n). 13. Explain what it means for a function to be O(1). 14. Give as good (i.e. small) a big-O estimate as possible for each of the following functions. a. (n² + 3n + 8)(n + 1) b. (3logn + 5n²)(n³ + 3n + 2)