UNIT-2

The Fundamentals-Algorithms, the Integers and Matrices: Algorithms, The Growth of Functions,
Complexity of Algorithms, The Integers and Division, Primes and Greatest Common Divisors, Integers
and Algorithms, Applications of Number Theory, Matrices.

Algorithm: A set of finite rules or instructions to be followed in calculations or other problem-

solving operations.
Example: Algorithm to add 3 numbers and print their sum:
1. START
2. Declare 3 integer variables num1, num2, and num3.
3. Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.
4. Declare an integer variable sum to store the resultant sum of the 3 numbers.
5. Add the 3 numbers and store the result in the variable sum.
6. Print the value of the variable sum
7. END

What is the need for algorithms?

1. Algorithms are necessary for solving complex problems efficiently and effectively.
2. They help to automate processes and make them more reliable, faster, and easier to perform.
3. Algorithms also enable computers to perform tasks that would be difficult or impossible for
humans to do manually.
4. They are used in various fields such as mathematics, computer science, engineering, finance, and
many others to optimize processes, analyze data, make predictions, and provide solutions to
problems.

Characteristics of an Algorithm

1. Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should be
clear in all aspects and must lead to only one meaning.
2. Input: An algorithm has zero or more inputs. Each that contains a fundamental operator must
accept zero or more inputs.
3. Output: An algorithm produces at least one output. Every instruction that contains a
fundamental operator must accept zero or more inputs.
4. Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions in an algorithm one can clearly understand
what is to be done. Every fundamental operator in instruction must be defined without any
ambiguity.
 5. Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every
instruction which contains a fundamental operator must be terminated within a finite amount of
time. Infinite loops or recursive functions without base conditions do not possess finiteness.
6. Effectiveness: An algorithm must be developed by using very basic, simple, and feasible
operations so that one can trace it out by using just paper and pencil.

The Growth of Functions:

1. Big O notation (O):
2. Big Omega notation (Ω)
3. Big Theta notation (Θ)

1. Big O notation (O):

 It is defined as upper bound and upper bound on an algorithm is the most amount of time
required (the worst case performance).
 Big O notation is used to describe the asymptotic upper bound. Mathematically,
 f(n) is O(g(n)) if there exist positive constant C and n0 such that,
f(n) <= Cg(n) for all n >= n0
n = used to give upper bound a function.
If a function is O(n), it is automatically O(n-square) as well.

Graphic example for Big O :

2. Big Omega notation (Ω) :

 It is define as lower bound and lower bound on an algorithm is the least amount of time
required ( the most efficient way possible, in other words best case).
 An asymptotic upper bound, Ω notation provides asymptotic lower bound.
 Let f(n) define running time of an algorithm; f(n) is said to be Ω(g (n)) if there exists positive
constant C and (n0) such that
f(n) >= Cg(n) for all n >= n0
n = used to given lower bound on a function
If a function is Ω(n-square) it is automatically Ω(n) as well.
Graphical example for Big Omega (Ω):
3. Big Theta notation (Θ) :
 It is define as tightest bound and tightest bound is the best of all the worst case times that the
algorithm can take.
 Let f(n) define running time of an algorithm. f(n) is said to
be Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n)).
C2g(n) <= f(n) <= C1g(n) for n >= n0

Graphic example of Big Theta (Θ):

Complexity of Algorithms:
1. Time Complexity
2. Space Complexity

1. Time Complexity : The time complexity of an algorithm is defined as the amount of time taken by
an algorithm to run as a function of the length of the input. Note that the time to run is a function of
the length of the input and not the actual execution time of the machine on which the algorithm is
running on.

How is Time complexity computed?

 If we have statements with basic operations like comparisons, return statements, assignments,
and reading a variable. We can assume they take constant time each O(1).

statement 1; if( a==5) return true; ------------------ executes1 time

statement 2; int x= 4>5 ? 1:0; ----------------------- executes1 time
statement 3; bool flag=true; ---------------------- executes1 time
This is the result of calculating the overall time complexity.

total time = time(statement1) + time(statement2) + ... time (statementN)

T(n) = 1+1+1
Overall, T(n)= O(1), which means constant complexity.

 For any loop, we find out the runtime of the block inside them and multiply it by the number of
times the program will repeat the loop.
for (int i = 0; i < n; i++) {
cout << “DMS” << endl;
}
 For the above example, the loop will execute n times, and it will print “DMS” N number of
times. so the time taken to run this program is:
T(N)= n *( t(cout statement))
= n * O(1)
=O(n), Linear complexity.
 For 2D arrays, we would have nested loop concepts, which means a loop inside a loop.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << “DMS” << endl;
}
}
For the above example, the cout statement will execute n*m times, and it will
print “GeeksForGeeks” N*M number of times. so the time taken to run this program is:
T(N)= n * m *(t(cout statement))
= n * m * O(1)
=O(n*m), Quadratic Complexity.

2. Space Complexity : The amount of memory required by the algorithm to solve a given problem is
called the space complexity of the algorithm. Problem-solving using a computer requires memory to
hold temporary data or final result while the program is in execution.

How is space complexity computed?

 The space Complexity of an algorithm is the total space taken by the algorithm with respect to
the input size. Space complexity includes both Auxiliary space and space used by input.
 Space complexity is a parallel concept to time complexity. If we need to create an array of size
n, this will require O(n) space. If we create a two-dimensional array of size n*n, this will
require O(n 2) space.
Example:
int add (int n){
if (n <= 0){
return 0;
}
return n
}
Here each call add a level to the stack :
1. Variables are n and retuen statement ,which si s(n)=1+1=O(2)

Different complexities:

The Integers and Division:

If a and b are integers with a ≠ 0, we say athat a divides b if there is an integer c such that b = ac (or

is a multiple of a. The notation a ∣ b denotes that a divides b. We write a does not divide b.
equivalently, if b / a is an integer). When a divides b we say that a is a factor or divisor of b, and that b

The division algorithm:

Modular arithmetic

Example: Determine whether 17 is congruent to 5 modulo 6.

Solution: To prove 17 ≡ 5 (mod 6). However, because
17 mod 6 = 5
5 mod 6 = 5
For 17 and 5 the remainder is same so 17 is congruent to 5 modulo 6

Primes and Greatest Common Divisors:

Prime :

Prime factorization:
Greatest Common Divisors and Least Common Multiples:

Example: Find the Greatest common Divisor of 24, 30 and 36.

Solution: Prime factors of 24 = 2 x 3 × 3
Prime factors of 30 = 2 × 3 × 5
Prime factors of 36 = 2 x 2 x 3 x 3
From the factorisation, we can see, only 2 x 3 are common prime factors.
Therefore, GCD (24, 30, 36) = 2 x 3 = 6

Example :
The Euclidean Algorithm:

The Euclidean algorithm, often known as Euclid's algorithm, is an effective way to

determine the greatest common divisor (GCD), or the biggest number that divides two
integers (numbers) evenly and without leaving a remainder.

ALGORITHM 1 The Euclidean Algorithm.

procedure gcd(a, b: positive integers)

x := a
y := b
while y ≠ 0
r := x mod y
x := y
y := r
return x{gcd(a, b) is x}

GCD as Linear Combinations:

An important result we will use throughout the remainder of this section is that the greatest common divisor
of two integers a and b can be expressed in the form sa + tb, where s and t are integers. In other words,
gcd(a, b) can be expressed as a linear combination with integer coefficients of a and b.
Solving Congurence:

T H E C HI N E S E R EM Let m1, m2, … , mn be pairwise relatively

pr im e po s it iv e in te ge r s a1, a2, … , an arbitrary integers. Then the system
A I N D E R T H E O R EM
x ≡ a1 (mod m1),
g re a te r th an o ne a n d
x ≡ a2 (mod m2),
⋅
⋅
⋅
x ≡ an (mod mn)
has a unique solution modulo m = m1m2 ⋯ mn. (That is, there is a solution x with
0 ≤ x < m, and all other solutions are congruent modulo m to this solution.)
Integers and Algorithms:
Example: Find the binary expansion of (241)10.
Solution: First divide 241 by 2 to obtain
241 = 2 ⋅ 120 + 1.
Successively dividing quotients by 2 gives
120 = 2 ⋅ 60 + 0,
60 = 2 ⋅ 30 + 0,
30 = 2 ⋅ 15 + 0,
15 = 2 ⋅ 7 + 1,
7 = 2 ⋅ 3 + 1,
3 = 2 ⋅ 1 + 1,
1 = 2 ⋅ 0 + 1.
The successive remainders that we have found, 1, 0, 0, 0, 1, 1, 1, 1, are the digits from the
right to the left in the binary (base 2) expansion of (241)10. Hence,
(241)10 = (1111 0001)2.

ALGORITHM 1 Constructing Base b Expansions.

procedure base b expansion(n, b: positive integers with b > 1)

q :=
nk
:= 0
while q ≠ 0
ak := q mod b
q := q div
b k := k +
1
return (ak−1, … , a1, a0) {(ak−1 … a1a0)b is the base b expansion of n}

Applications of Number Theory:

1. Hashing function
2. Pseudorandom number
3. Cryptography

1. Hashing Function: Hashing refers to the process of generating a fixed-size output from an input of
variable size using the mathematical formulas known as hash functions. This technique determines an
index or location for the storage of an item in a data structure.

h(k) = k mod m

Example: Arrange 11,12,13,14,15 in hash table m=10.

Solution: k =11,12,13,14,15
m =10
11 mod 10 = 1
12 mod 10 = 2
13 mod 10 = 3
 14 mod 10 = 4
15 mod 10 = 5

2.Pseudorandom number : The most commonly used procedure for generating pseudorandom numbers
is the linear congruential method. We choose four integers: the modulus m, multiplier a, increment c, and
seed x0, with2 ≤ a < m,0 ≤ c < m, and 0 ≤ x0 < m. We generate a sequence of pseudorandom numbers {xn},
with0 ≤ xn < m for all n, by successively using the recursively defined function

xn+1 = (axn + c) mod m.

Example: Find the sequence of pseudorandom numbers generated by the linear congruential
method with modulus m = 9, multiplier a = 7, increment c = 4, and seed x0 = 3.
Solution: We compute the terms of this sequence by successively using the recursively defined
function xn+1 = (7xn + 4) mod 9, beginning by inserting the seed x0 = 3 to find x1. We find that
x1 = 7x0 + 4 mod 9 = 7 ⋅ 3 + 4 mod 9 = 25 mod 9 = 7,
x2 = 7x1 + 4 mod 9 = 7 ⋅ 7 + 4 mod 9 = 53 mod 9 = 8,
x3 = 7x2 + 4 mod 9 = 7 ⋅ 8 + 4 mod 9 = 60 mod 9 = 6,
x4 = 7x3 + 4 mod 9 = 7 ⋅ 6 + 4 mod 9 = 46 mod 9 = 1,
x5 = 7x4 + 4 mod 9 = 7 ⋅ 1 + 4 mod 9 = 11 mod 9 = 2,
x6 = 7x5 + 4 mod 9 = 7 ⋅ 2 + 4 mod 9 = 18 mod 9 = 0,
x7 = 7x6 + 4 mod 9 = 7 ⋅ 0 + 4 mod 9 = 4 mod 9 = 4,
x8 = 7x7 + 4 mod 9 = 7 ⋅ 4 + 4 mod 9 = 32 mod 9 = 5,
x9 = 7x8 + 4 mod 9 = 7 ⋅ 5 + 4 mod 9 = 39 mod 9 = 3.
Because x9 = x0 and because each term depends only on the previous term, we see that the
sequence 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, …

3. Cryptography: For instance, using this scheme the letter B is sent to E and the letter X is sent to A. This is
an example of encryption, that is, the process of making a message secret. To express Caesar’s encryption
process mathematically, by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f (p) in
the set
{0, 1, 2, … , 25} with

f ( p) = ( p + 3) mod 26.

Example: What is the secret message produced from the message “MEET YOU IN THE PARK”
using the Caesar cipher?
Solution: First replace the letters in the message with numbers. This produces
12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10.
Now replace each of these numbers p by f (p) = (p + 3) mod 26. This gives
 1 5 7 7 22 1 17 23 11 16 22 107 183 20 13.
Translating this back to letters produces the encrypted message “PHHW BRX LQ WKH SDUN.”

RSA Algorithm:
One of the application of number theory. Encryption proceeds by transforming each block mi to a ciphertext
block ci. This is done using the function.
c = me mod n.

Example: Encrypt the message STOP using the RSA cryptosystem with key (2537, 13). Note that 2537 =
43 ⋅ 59, p = 43 and q = 59 are primes, and gcd(e, (p − 1)(q − 1)) = gcd(13, 42 ⋅ 58) = 1.

Solution: To encrypt, we first translate the letters in STOP into their numerical equivalents. We
then group these numbers into blocks of four
ST OP
1819 1415.
We encrypt each block using the mapping
c = m13 mod 2537.
Comp utations using fast modular multiplication show that
13
181913 mod 2537 = 2081
1415 mod 2537 = 2182.
13

The encrypted message is 2081 2182.

Matrices:
Matrices are rectangular arrays of numbers, symbols, or characters where all of these elements are arranged in
each row and column. An array is a collection of items arranged at different locations.
1. Addition of Matrices: In addition of matrices, the elements of two matrices are added to yield a
matrix that contains elements obtained as the sum of two matrices. The addition of matrices is
performed between two matrices of the same order.
Multiplication of Matrices: In the multiplication of matrices, two matrices are multiplied to yield a single
equivalent matrix. The multiplication is performed in the manner that the elements of the row of the first
matrix multiply with the elements of the columns of the second matrix and the product of elements are added
to yield a single element of the equivalent matrix. If a matrix [A]i⨯j is multiplied with matrix [B]j⨯k then the
product is given as [AB]i⨯k.