# Functions and Algorithms: Best Answers 007EH

Welcome to **Lesson Five- Functions and Algorithms**.

You can also join the **Discrete Mathematics Forum **to interact and share ideas, also you can navigate to any session using the **Table of Content **

Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.

# Introduction to Functions and Algorithms

# Functions and Algorithms

It is a mapping in which every element of set A is uniquely associated at the element with set B. The set of A is called Domain of a function and set of B is called Co domain.

## Domain, Co-Domain, and Range of a Function:

**Domain of a Function:** Let f be a function from P to Q. The set P is called the domain of the function f.

**Co-Domain of a Function:** Let f be a function from P to Q. The set Q is called Co-domain of the function f.

**Range of a Function:** The range of a function is the set of picture of its domain. In other words, we can say it is a subset of its co-domain. It is denoted as f (domain).

- If f: P → Q, then f (P) = {f(x): x ∈ P} = {y: y ∈ Q | ∃ x ∈ P, such that f (x) = y}.

**Example:** Find the Domain, Co-Domain, and Range of function.

- Let x = {1, 2, 3, 4}
- y = {a, b, c, d, e}
- f = {(1, b), (2, a), (3, d), (4, c)

**Solution:**

Domain of function: {1, 2, 3, 4} Range of function: {a, b, c, d} Co-Domain of function: {a, b, c, d, e}

## Functions as a Set

If P and Q are two non-empty sets, then a function f from P to Q is a subset of P x Q, with two important restrictions

- ∀ a ∈ P, (a, b) ∈ f for some b ∈ Q
- If (a, b) ∈ f and (a, c) ∈ f then b = c.

#### Note1: There may be some elements of the Q which are not related to any element of set P.

#### 2. Every element of P must be related with at least one element of Q.

**Example1:** If a set A has n elements, how many functions are there from A to A?

**Solution:** If a set A has n elements, then there are n^{n} functions from A to A.

## Representation of a Function

The two sets P and Q are represented by two circles. The function f: P → Q is represented by a collection of arrows joining the points which represent the elements of P and corresponds elements of Q

**Example1:**

- Let X = {a, b, c} and Y = {x, y, z} and f: X → Y such that
- f= {(a, x), (b, z), (c, x)}

Then f can be represented diagrammatically as follows

**Example2:** Let X = {x, y, z, k} and Y = {1, 2, 3, 4}. Determine which of the following functions. Give reasons if it is not. Find range if it is a function.

- f = {(x, 1), (y, 2), (z, 3), (k, 4)
- g = {(x, 1), (y, 1), (k, 4)
- h = {(x, 1), (x, 2), (x, 3), (x, 4)
- l = {(x, 1), (y, 1), (z, 1), (k, 1)}
- d = {(x, 1), (y, 2), (y, 3), (z, 4), (z, 4)}.

**Solution:**

- It is a function. Range (f) = {1, 2, 3, 4}
- It is not a function because every element of X does not relate with some element of Y i.e., Z is not related with any element of Y.
- h is not a function because h (x) = {1, 2, 3, 4} i.e., element x has more than one image in set Y.
- d is not a function because d (y) = {2, 3} i.e., element y has more than image in set Y.

# Types of Functions

**1. Injective (One-to-One) Functions:** A function in which one element of Domain Set is connected to one element of Co-Domain Set.

**2. Surjective (Onto) Functions:** A function in which every element of Co-Domain Set has one pre-image.

**Example:** Consider, A = {1, 2, 3, 4}, B = {a, b, c} and f = {(1, b), (2, a), (3, c), (4, c)}.

It is a Surjective Function, as every element of B is the image of some A

#### Note: In an Onto Function, Range is equal to Co-Domain.

**3. Bijective (One-to-One Onto) Functions:** A function which is both injective (one to – one) and surjective (onto) is called bijective (One-to-One Onto) Function.

**Example:**

- Consider P = {x, y, z}
- Q = {a, b, c}
- and f: P → Q such that
- f = {(x, a), (y, b), (z, c)}

The f is a one-to-one function and also it is onto. So it is a bijective function.

**4. Into Functions:** A function in which there must be an element of co-domain Y does not have a pre-image in domain X.

**Example:**

- Consider, A = {a, b, c}
- B = {1, 2, 3, 4} and f: A → B such that
- f = {(a, 1), (b, 2), (c, 3)}
- In the function f, the range i.e., {1, 2, 3} ≠ co-domain of Y i.e., {1, 2, 3, 4}

Therefore, it is an into function

**5. One-One Into Functions:** Let f: X → Y. The function f is called one-one into function if different elements of X have different unique images of Y.

**Example:**

- Consider, X = {k, l, m}
- Y = {1, 2, 3, 4} and f: X → Y such that
- f = {(k, 1), (l, 3), (m, 4)}

The function f is a one-one into function

**6. Many-One Functions:** Let f: X → Y. The function f is said to be many-one functions if there exist two or more than two different elements in X having the same image in Y.

**Example:**

- Consider X = {1, 2, 3, 4, 5}
- Y = {x, y, z} and f: X → Y such that
- f = {(1, x), (2, x), (3, x), (4, y), (5, z)}

The function f is a many-one function

**7. Many-One Into Functions:** Let f: X → Y. The function f is called the many-one function if and only if is both many one and into function.

**Example:**

- Consider X = {a, b, c}
- Y = {1, 2} and f: X → Y such that
- f = {(a, 1), (b, 1), (c, 1)}

As the function f is a many-one and into, so it is a many-one into function.

**8. Many-One Onto Functions:** Let f: X → Y. The function f is called many-one onto function if and only if is both many one and onto.

**Example:**

- Consider X = {1, 2, 3, 4}
- Y = {k, l} and f: X → Y such that
- f = {(1, k), (2, k), (3, l), (4, l)}

The function f is a many-one (as the two elements have the same image in Y) and it is onto (as every element of Y is the image of some element X). So, it is many-one onto function

# Identity Functions

The function f is called the identity function if each element of set A has an image on itself i.e. f (a) = a ∀ a ∈ A.

It is denoted by I.

**Example**

- Consider, A = {1, 2, 3, 4, 5} and f: A → A such that
- f = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}.

The function f is an identity function as each element of A is mapped onto itself. The function f is a one-one and onto

## Invertible (Inverse) Functions

A function f: X → Y is invertible if and only if it is a bijective function.

Consider the bijective (one to one onto) function f: X → Y. As f is a one to one, therefore, each element of X corresponds to a distinct element of Y. As f is onto, there is no element of Y which is not the image of any element of X, i.e., range = co-domain Y.

The inverse function for f exists if f^{-1} is a function from Y to X.

**Example:**

- Consider, X = {1, 2, 3}
- Y = {k, l, m} and f: X→Y such that
- f = {(1, k), (2, m), (3, l)

The inverse function of f is shown in fig:

# Compositions of Functions

Consider functions, f: A → B and g: B → C. The composition of f with g is a function from A into C defined by (gof) (x) = g [f(x)] and is defined by gof.

To find the composition of f and g, first find the image of x under f and then find the image of f (x) under g.

**Example1:**

- Let X = {1, 2, 3}
- Y = {a, b}
- Z = {5, 6, 7}.

Consider the function f = {(1, a), (2, a), (3, b)} and g = {(a, 5), (b, 7)} as in figure. Find the composition of gof.

**Solution:** The composition function gof is shown in fig:

(gof) (1) = g [f (1)] = g (a) = 5, (gof) (2) = g [f (2)] = g (a) = 5 (gof) (3) = g [f (3)] = g (b) = 7.

**Example2:** Consider f, g and h, all functions on the integers, by f (n) =n^{2}, g (n) = n + 1 and h (n) = n – 1.

Determine **(i)** hofog **(ii)** gofoh **(iii)** fogoh.

**Solution:**

(i) hofog (n) = n + 1, hofog (n + 1) = (n+1)^{2}h [(n+1)^{2}] = (n+1)^{2}- 1 = n^{2}+ 1 + 2n - 1 = n^{2}+ 2n. (ii) gofoh (n) = n - 1, gof (n - 1) = (n-1)^{2}g [(n-1)^{2}] = (n-1)^{2}+ 1 = n^{2}+ 1 - 2n + 1 = n^{2}- 2n + 2. (iii) fogoh (n) = n - 1 fog (n - 1) = (n - 1) + 1 f (n) = n^{2}.

**Note:**

- If f and g are one-to-one, then the function (gof) (gof) is also one-to-one.
- If f and g are onto then the function (gof) (gof) is also onto.
- Composition consistently holds associative property but does not hold commutative property.

# Mathematical Functions

The following are the functions which are widely used in computer science.

**1. Floor Functions:** The floor function for any real number x is defined as f (x) is the greatest integer 1 less than or equal to x. It is denoted by [x].

**Example:** Determine the value of

**(i)**[3. 5] **(ii)**[-2.4] **(iii)**[3. 143].

**Solution:**

(i)[3 . 5] = 3 (ii) [-2 .4] = -3 (iii) [3. 143] = 3

**2. Ceiling Functions:** The ceiling function for any real number x is defined as h (x) is the smallest integer greater than or equal to x. It is denoted by [x].

**Example:** Determine the value of

**(i)**[3. 5] **(ii)** [-2.4] **(iii)** [3. 143].

**Solution:**

(i)[3. 5] = 4 (ii) [-2 .4] = -2 (iii) [3. 143] = 4.

**3. Remainder Functions:** The integer remainder is obtained when some a is divided by m. It is denoted by a (MOD m). We can also define it as, a (MOD m) is the unique integer t such that a = Mq + t. Here q is quotient 0 ≤ r < M.

**Example:** Determine the value of the following:

**(i)** 35 (MOD 7) **(ii)** 20 (MOD 3) **(iii)** 4 (MOD 9)

**Solution:**

(i) 35 (MOD 7) = 0 (ii) 20 (MOD 3) = 2 (iii) 4 (MOD 9) = 4

**4. Exponential Functions:** Consider two sets A and B. Let A = B = I_{+} and also let f: A → B be defined by f (n) = k^{n}. Here n is a +ve integer. The function f is called the base k exponential function.

#### Note1: k^{t}= k. k. k…….k (t times).

2: k^{0}=1,k^{-M}=

3. For rational number, a/b, the exponential function is

**Example:** Determine the value of the following:

**(i)** 10^{3} **(ii)** 5^{1/2} **(iii)** 3^{-5}

**Solution:**

10^{3}= 10. 10. 10 = 1000 5^{1/2}=2.23607 3^{-5}=

**5. Logarithmic Functions:** Consider two sets A and B. Let A = B = R (the set of real numbers and also let f_n:A→B be defined for each positive integer n > 1 as f_{n} (x)=log_{n}(x) the base n of x.

#### Note1: k = log_{n} x and n^{k} are equivalent.

2. For any base n, log_{n} 1=0 as n^{0}=1.

3. For any base n, log_{n} n=1 as n^{1}=n.

**Example:** Determine the value of the following:

**(i)** log_{2}?16 **(ii)** log_{2} 100 **(iii)** log_2 0.001.

**Solution:**

(i)log_{2}16 = 4 as 2^{4}=16. (ii)log_{2}100 = 6 as 2^{6}= 64 but 2^{7}=128 which is greater (iii)log_{2}0.001=-9 as 2^{-9}=but 2^{-10}=which is greater.

# Algorithms and Functions

**Algorithm:** An algorithm is a step-by-step method for solving some problem.

### Characteristics of Algorithms:

Algorithms generally have the following characteristics:

**Input:**The algorithm receives input. Zero or more quantities are externally supplied.**Output:**The algorithm produces output. At least one quantity is produced.**Precision:**The steps are precisely stated. Each instruction is clear and unambiguous.**Feasibility:**It must be feasible to execute each instruction.**Flexibility:**It should also be possible to make changes in the algorithm without putting so much effort on it.**Generality:**The algorithm applies to a set of inputs.**Finiteness:**Algorithm must complete after a finite number of instruction have been executed.

## Analysis (Complexity) of Algorithms

The Analysis of an algorithm refers to the process of deriving estimates for the time and space needed to execute the algorithm.

It is important to estimate the time (e.g., the number of steps) and space (e.g., the number of variables) required by algorithms. Knowing the time and space required by algorithm allows us to compare the algorithms that solve the same problem. For example, if one algorithm takes n steps to solve a problem and another algorithm takes n^2 steps to solve the same problem, we would prefer the first algorithm. This estimation of time and space needed to execute the algorithm is called the time and space complexity of the algorithm.

The time required to execute an algorithm is a function of the input. Instead of dealing directly with the input, parameters are used to characterize the size of the input. e.g. if the input is a set containing n elements, the size of the input n. There are three cases worth noting about the time complexity of an algorithm since determining the exact time complexity of an algorithm in a difficult task.

**Worst-case: f (n)**represent by the maximum number of steps taken on any instance of size n.**Best-case: f (n)**represent by the minimum number of steps taken on any instance of size n.**Average case: f (n)**represent by the average number of steps taken on any instance of size n.

## Asymptotic Notations

Asymptotic Notations are used to describe the execution time of an algorithm. The notations show the order of growth of functions. Here the time taken by an algorithm is mapped regarding mathematical functions. There are many asymptotic notations like 0, θ, Ω,w each having its importance.

**1. Big-oh notation:** The function **f (n) =O (g (n))** [read as “f of n is big-oh of g of n”] if and only if exist positive constant c and n_{0} such that

f (n) ⩽ C x g (n) for all n, n ≥ n_{0}

**Example1:** The function 4n + 3 = O (n) as 4n + 3 ⩽ 5n for all n ≥.

**Example2:** The function 20n^{2} + 5n + 2 = O (n^{2}) as 20n^{2}+ 5n +2⩽21n^{2} for all n ≥.

**2. Omega (Ω) Notation:** The function f (n) = Ω (g (n)) [read as “f of n is omega of g of n”] if and only if there exists positive constant c and n_{0} such that

f (n) ≥ C* g (n) for all n, n ≥ n_{0}

**Example1:** The function 4n + 3 = Ω (n) as 4n + 3 ≥ 4n for all n ≥1.

**Example2:** The function 20n^{2}+ 5n +2 = Ω (n) as 20n^{2}+ 5n +2 ≥ 20n^{2} for all n ≥1.

**3. Theta (θ):** The function f (n) = θ (g (n)) [read as “f is the theta of g of n”] if and only if there exists positive constant k_{1}, k_{2} and k_{0} such that

k_{1}* g (n) ≤ f (n)≤k_{2}* g(n)for all n, n≥n_{0}

**Example1:** The function 4n + 3 = θ (n) as 4n + 3 ≥ 4n for all n ≥ 3 and 4n + 3 ≤ 5n for all n ≥ 3.

**Example2:** The function 20n^{2}+ 5n +2 = θ (n^{2}) as 20n^{2}+ 5n +2 ≤ 21n^{2} for all n ≥1 and 20n^{2}+ 5n +2 ≥ 20n^{2} for all n ≥ 1.

## Responses