Define Algorithm:

” A set of finite rules or instructions to be followed in calculations or other problem-solving

operations ”
Or
” A procedure for solving a mathematical problem in a finite number of steps that
frequently involves recursive operations”.

An algorithm is defined as complex based on the amount of Space and Time it consumes.
Hence the Complexity of an algorithm refers to the measure of the time that it will need to
execute and get the expected output, and the Space it will need to store all the data (input,
temporary data, and output).

Algorithms form the basis of computer programming and are used to solve problems
ranging from simple sorting and searching to complex tasks such as artificial intelligence
and machine learning.

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.
 All algorithms must satisfy the following criteria
Input. An algorithm has zero or more inputs, taken or collected from a specified set of
objects.
Output. An algorithm has one or more outputs having a specific relation to the inputs.
Definiteness. Each step must be clearly defined; Each instruction must be clear and
unambiguous.
Finiteness. The algorithm must always finish or terminate after a finite number of steps.
Effectiveness. All operations to be accomplished must be sufficiently basic that they can be
done exactly and in finite length.
Example:

An algorithm to find sum of n natural numbers

Algorithm. input number n

Step 1: Start

Step 2: Read number n

Step 3: Declare sum to 0 and i to 1

Step 4: Repeat steps 5 to 7 until i<=n

 Step 5: update sum as sum = sum + i

Step 6: increment i Step 7: Print sum

Step 8: Stop Output: sum.

Pseudocode is a way of expressing an algorithm without conforming to specific syntax

rules. By learning to read and write pseudocode, you can easily communicate ideas and
concepts to other programmers, even though they may be using completely different
languages.

Pseudocode is the intermediate state between an idea and its implementation(code) in

a high-level language.

Pseudocode of addition of two numbers

 Begin.
 WRITE “Please enter two numbers to add”
 READ num1.
 READ num2.
 Sum = num1+num2.
 WRITE Sum.
 End.

Pseudocode for finding eligibility for voting

Begin.
WRITE “Please enter your age”
READ age.
 IF age>18
Write “You are eligible”
ELSE
write “not eligiblefor voting”
End.

https://youtu.be/Espr3UdCd4U

Performance Analysis

Algorithm analysis is the process of evaluating the performance of an algorithm, usually in

terms of its time and space complexity.

Performance analysis of an algorithm is the process of calculating space and time required
by that algorithm.

Performance analysis of an algorithm is performed by using the following measures...

1. Space required to complete the task of that algorithm (Space Complexity). It

includes program space and data space

2. Time required to complete the task of that algorithm (Time Complexity)

What is Space complexity?

When we design an algorithm to solve a problem, it needs some computer memory to
complete its execution. For any algorithm, memory is required for the following purposes...
1. To store program instructions.
2. To store constant values.
3. To store variable values.
4. And for few other things like funcion calls, jumping statements etc,.
Space complexity of an algorithm can be defined as follows...
Total amount of computer memory required by an algorithm to complete its execution is
called as space complexity of that algorithm.

Example:

int square(int a)
{
 return a*a;
}
In the above piece of code, it requires 2 bytes of memory to store variable 'a' and another 2 bytes of memory is
used for return value.
That means, totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of memory
is fixed for any input value of 'a'. This space complexity is said to be Constant Space Complexity.

What is Time complexity?

Every algorithm requires some amount of computer time to execute its instruction to perform the task. This
computer time required is called time complexity.
The time complexity of an algorithm can be defined as follows...

The time complexity of an algorithm is the total amount of time required by an algorithm to complete its
execution.

Generally, the running time of an algorithm depends upon the following...

1. Whether it is running on Single processor machine or Multi processor machine.
2. Whether it is a 32 bit machine or 64 bit machine.
3. Read and Write speed of the machine.
4. The amount of time required by an algorithm to
perform Arithmetic operations, logical operations, return value and assignment operations etc.,
5. Input data
To calculate the time complexity of an algorithm, we need to define a model machine. Let us assume a
machine with following configuration...
1. It is a Single processor machine
2. It is a 32 bit Operating System machine
3. It performs sequential execution
4. It requires 1 unit of time for Arithmetic and Logical operations
5. It requires 1 unit of time for Assignment and Return value
6. It requires 1 unit of time for Read and Write operations
Example:
int sum(int a, int b)
{
return a+b;}
The above code requires 1 unit of time to calculate a+b and 1 unit of time to return the value. That means,
totally it takes 2 units of time to complete its execution. And it does not change based on the input values of a
and b. That means for all input values, it requires the same amount of time i.e. 2 units.

Asymptotic notation

Asymptotic notation of an algorithm is a mathematical representation of its complexity.

we use THREE types of Asymptotic Notations and those are as follows...

1. Big - Oh (O)
2. Big - Omega (Ω)
 3. Big - Theta (Θ)
Big - Oh Notation (O)

Big - Oh notation is used to define the upper bound of an algorithm in terms of Time Complexity.
That means Big - Oh notation always indicates the maximum time required by an algorithm for all input values.
That means Big - Oh notation describes the worst case of an algorithm time complexity.
Big - Oh Notation can be defined as follows...

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) <=
C g(n) for all n >= n , C > 0 and n >= 1. Then we can represent f(n) as O(g(n)).
0 0

f(n) = O(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time
required is on Y-Axis

In above graph after a particular input value n 0, always C g(n) is greater than f(n) which indicates the
algorithm's upper bound.

Big - Omege Notation (Ω)

Big - Omega notation is used to define the lower bound of an algorithm in terms of Time Complexity.
That means Big-Omega notation always indicates the minimum time required by an algorithm for all input
values. That means Big-Omega notation describes the best case of an algorithm time complexity.
Big - Omega Notation can be defined as follows...

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If f(n) >=
C g(n) for all n >= n , C > 0 and n >= 1. Then we can represent f(n) as Ω(g(n)).
0 0

f(n) = Ω(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time
required is on Y-Axis
In above graph after a particular input value n 0, always C g(n) is less than f(n) which indicates the algorithm's
lower bound.

ig - Theta Notation (Θ)

Big - Theta notation is used to define the average bound of an algorithm in terms of Time Complexity.
That means Big - Theta notation always indicates the average time required by an algorithm for all input values.
That means Big - Theta notation describes the average case of an algorithm time complexity.
Big - Theta Notation can be defined as follows...

Consider function f(n) as time complexity of an algorithm and g(n) is the most significant term. If C g(n)1

<= f(n) <= C g(n) for all n >= n , C > 0, C > 0 and n >= 1. Then we can represent f(n) as Θ(g(n)).
2 0 1 2 0

f(n) = Θ(g(n))

Consider the following graph drawn for the values of f(n) and C g(n) for input (n) value on X-Axis and time
required is on Y-Axis
In above graph after a particular input value n 0, always C1 g(n) is less than f(n) and C 2 g(n) is greater than f(n)
which indicates the algorithm's average bound.

http://www.btechsmartclass.com/data_structures/linear-non-linear-data-
structures.html

Performance measurement: time and space complexity

Randomized Algorithms:

These algorithms introduce randomness to improve efficiency or simplify the

algorithm design. By incorporating random choices into their processes,
randomized algorithms can often provide faster solutions or better approximations
compared to deterministic algorithms. They are particularly useful in situations
where exact solutions are difficult to find or when a probabilistic approach is
acceptable.

For example, in Randomized Quick Sort, we use a random number to pick the next
pivot (or we randomly shuffle the array).
https://www.javatpoint.com/quick-sort