0.7 Discrete structures function  (Page 2/5)

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.

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.