<< Chapter < Page Chapter >> Page >

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.

Questions & Answers

what is microbiology
Agebe Reply
What is a cell
Odelana Reply
what is cell
Mohammed
how does Neisseria cause meningitis
Nyibol Reply
what is microbiologist
Muhammad Reply
what is errata
Muhammad
is the branch of biology that deals with the study of microorganisms.
Ntefuni Reply
What is microbiology
Mercy Reply
studies of microbes
Louisiaste
when we takee the specimen which lumbar,spin,
Ziyad Reply
How bacteria create energy to survive?
Muhamad Reply
Bacteria doesn't produce energy they are dependent upon their substrate in case of lack of nutrients they are able to make spores which helps them to sustain in harsh environments
_Adnan
But not all bacteria make spores, l mean Eukaryotic cells have Mitochondria which acts as powerhouse for them, since bacteria don't have it, what is the substitution for it?
Muhamad
they make spores
Louisiaste
what is sporadic nd endemic, epidemic
Aminu Reply
the significance of food webs for disease transmission
Abreham
food webs brings about an infection as an individual depends on number of diseased foods or carriers dully.
Mark
explain assimilatory nitrate reduction
Esinniobiwa Reply
Assimilatory nitrate reduction is a process that occurs in some microorganisms, such as bacteria and archaea, in which nitrate (NO3-) is reduced to nitrite (NO2-), and then further reduced to ammonia (NH3).
Elkana
This process is called assimilatory nitrate reduction because the nitrogen that is produced is incorporated in the cells of microorganisms where it can be used in the synthesis of amino acids and other nitrogen products
Elkana
Examples of thermophilic organisms
Shu Reply
Give Examples of thermophilic organisms
Shu
advantages of normal Flora to the host
Micheal Reply
Prevent foreign microbes to the host
Abubakar
they provide healthier benefits to their hosts
ayesha
They are friends to host only when Host immune system is strong and become enemies when the host immune system is weakened . very bad relationship!
Mark
what is cell
faisal Reply
cell is the smallest unit of life
Fauziya
cell is the smallest unit of life
Akanni
ok
Innocent
cell is the structural and functional unit of life
Hasan
is the fundamental units of Life
Musa
what are emergency diseases
Micheal Reply
There are nothing like emergency disease but there are some common medical emergency which can occur simultaneously like Bleeding,heart attack,Breathing difficulties,severe pain heart stock.Hope you will get my point .Have a nice day ❣️
_Adnan
define infection ,prevention and control
Innocent
I think infection prevention and control is the avoidance of all things we do that gives out break of infections and promotion of health practices that promote life
Lubega
Heyy Lubega hussein where are u from?
_Adnan
en français
Adama
which site have a normal flora
ESTHER Reply
Many sites of the body have it Skin Nasal cavity Oral cavity Gastro intestinal tract
Safaa
skin
Asiina
skin,Oral,Nasal,GIt
Sadik
How can Commensal can Bacteria change into pathogen?
Sadik
How can Commensal Bacteria change into pathogen?
Sadik
all
Tesfaye
by fussion
Asiina
what are the advantages of normal Flora to the host
Micheal
what are the ways of control and prevention of nosocomial infection in the hospital
Micheal
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete structures. OpenStax CNX. Jan 23, 2008 Download for free at http://cnx.org/content/col10513/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask