What is an Algorithm?

An algorithm is a step by step procedure to solve a problem. In normal language, the algorithm is
defined as a sequence of statements which are used to perform a task. In computer science, an
algorithm can be defined as follows...
An algorithm is a sequence of instructions used for solving a problem, which can be implemented (as a
program) on a computer.

Algorithms are used to convert our problem solution into step by step statements. These statements
can be converted into computer programming instructions which form a program. This program is
executed by a computer to produce a solution. Here, the program takes required data as input,
processes data according to the program instructions and finally produces a result as shown in the
following picture.

Specifications of Algorithms
Every algorithm must satisfy the following specifications...
1. Input - Every algorithm must take zero or more number of input values from external.
2. Output - Every algorithm must produce an output as result.
3. Definiteness - Every statement/instruction in an algorithm must be clear and unambiguous (only
one interpretation).
4. Finiteness - For all different cases, the algorithm must produce result within a finite number of
steps.
5. Effectiveness - Every instruction must be basic enough to be carried out and it also must be
feasible.

Recursive Algorithm
In computer science, all algorithms are implemented with programming language functions. We can
view a function as something that is invoked (called) by another function. It executes its code and then

Prof. Hasnain Aslam Page 1

returns control to the calling function. Here, a function can be called by itself or it may call another
function which in turn call the same function inside it is known as recursion. A recursive function can be
defined as follows...

The function which is called by itself is known as Direct Recursive function (or Recursive function)

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where
algorithms are used include:

1. Computer Science: 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.
2. Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine
learning, and are used to develop intelligent systems that can perform tasks such as image
recognition, natural language processing, and decision-making.

Advantages of Algorithms:
1. It is easy to understand.
2. An algorithm is a step-wise representation of a solution to a given problem.
3. In an Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for
the programmer to convert it into an actual program.

Disadvantages of Algorithms:
1. Writing an algorithm takes a long time so it is time-consuming.
2. Understanding complex logic through algorithms can be very difficult.
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

Prof. Hasnain Aslam Page 2

What is Performance, Analysis of an algorithm?
If we want to go from city "A" to city "B", there can be many ways of doing this. We can go by flight, by
bus, by train and also by bicycle. Depending on the availability and convenience, we choose the one
which suits us. Similarly, in computer science, there are multiple algorithms to solve a problem. When
we have more than one algorithm to solve a problem, we need to select the best one. Performance
analysis helps us to select the best algorithm from multiple algorithms to solve a problem.
When there are multiple alternative algorithms to solve a problem, we analyze them and pick the one
which is best suitable for our requirements. The formal definition is as follows...
Performance of an algorithm is a process of making evaluative judgment about algorithms.
Or
Performance of an algorithm means predicting the resources which are required to an algorithm to
perform its task.
That means when we have multiple algorithms to solve a problem, we need to select a suitable
algorithm to solve that problem.
We compare algorithms with each other which are solving the same problem, to select the best
algorithm. To compare algorithms, we use a set of parameters or set of elements like memory required
by that algorithm, the execution speed of that algorithm, easy to understand, easy to implement, etc.,
Generally, the performance of an algorithm depends on the following elements...

1. Whether that algorithm is providing the exact solution for the problem?
2. Whether it is easy to understand?
3. Whether it is easy to implement?
4. How much space (memory) it requires to solve the problem?
5. How much time it takes to solve the problem? Etc.,

When we want to analyze an algorithm, we consider only the space and time required by that particular
algorithm and we ignore all the remaining elements.
Based on this information, performance analysis of an algorithm can also be defined as follows...

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...

Prof. Hasnain Aslam Page 3

 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.

 If any algorithm requires a fixed amount of space for all input values then that space complexity
is said to be constant space complexity.
 If the amount of space required by an algorithm is increased with the increase of input value,
then that space complexity is said to be linear 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.,

Prof. Hasnain Aslam Page 4

 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

If any program requires a fixed amount of time for all input values then its time complexity is said to be
constant time complexity
If the amount of time required by an algorithm is increased with the increase of input value then that
time complexity is said to be linear time complexity.
Measurement:
 A Priori Analysis (Theoretical): This involves analyzing the algorithm mathematically to
determine its time and space complexity before actually running it. It relies on theoretical
models and asymptotic notations to predict performance.
 A Posteriori Testing (Experimental): This involves running the algorithm on a specific system
with various input sizes and collecting actual statistics on its execution time and memory
usage. This provides empirical data about the algorithm's performance in a real-world
environment.

Prof. Hasnain Aslam Page 5

What is Asymptotic Notation?
Whenever we want to perform analysis of an algorithm, we need to calculate the complexity of that
algorithm. But when we calculate the complexity of an algorithm it does not provide the exact amount
of resource required. So instead of taking the exact amount of resource, we represent that complexity in
a general form (Notation) which produces the basic nature of that algorithm. We use that general form
(Notation) for analysis process.
Asymptotic notation of an algorithm is a mathematical representation of its complexity.
Majorly, 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.
Many times we easily find an upper bound by simply looking at the algorithm.
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 0<
f(n) <= C g(n) for all n >= n0, C > 0 and n0 >= 1.
Then we can represent f(n) as O(g(n)).
f(n) = O(g(n))

Prof. Hasnain Aslam Page 6

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 >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as Ω(g(n)).
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 n0, always C g(n) is less than f(n) which indicates the
algorithm's lower bound.

Big - 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
C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1. Then we can represent f(n) as Θ(g(n)).
f(n) = Θ(g(n))

Prof. Hasnain Aslam Page 7

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 n0, always C1 g(n) is less than f(n) and C2 g(n) is greater than
f(n) which indicates the algorithm's average bound.

Asymptotic notation is mathematical shorthand used in computer science to describe the efficiency
and performance of algorithms as the input size (n) grows very large. It focuses on the primary growth
trend of an algorithm's time or space complexity, ignoring machine-specific constants and smaller
terms.

The main types of asymptotic notations are:

 Big-O Notation (O): Asymptotic Upper Bound (Worst Case)

Big-O describes the worst-case running time or the maximum amount of time an algorithm
might take to complete. It provides an upper bound on the growth rate of a function.
 Big-Omega Notation (Ω): Asymptotic Lower Bound (Best Case)
Big-Omega describes the best-case running time or the minimum amount of time an algorithm
will take. It provides a lower bound on the growth rate of a function.
 Big-Theta Notation (Θ): Asymptotic Tight Bond (Average Case)
Big-Theta describes the average-case running time, providing both a lower and an upper bound
that "tightly" encloses the function's growth.

Common Asymptotic Runtimes

The efficiency of algorithms is often categorized using these common runtimes, from fastest to slowest:
𝑂(1) Constant time

Prof. Hasnain Aslam Page 8

𝑂(log𝑛) Logarithmic time (e.g., binary search)
𝑂(𝑛) Linear time
𝑂(𝑛2) Quadratic time (e.g., simple sorting algorithms like insertion sort, bubble sort)

Prof. Hasnain Aslam Page 9

Prof. Hasnain Aslam Page 10
Prof. Hasnain Aslam Page 11