CIT 310 MODULE 1
MODULE 1 BASIC ALGORITHMIC ANALYSIS
UNIT 1 BASIC ALGORITHM CONCEPTS
1.0 Introduction
2.0 Objectives
3.0 What is an Algorithm?
3.1 Characteristics of an Algorithm
3.1.1 Advantages of Algorithms
3.1.2 Disadvantages of Algorithms
3.2 Pseudocode
3.2.1 Advantages of Pseudocode
3.2.2 Disadvantages of Pseudocode
3.2.3 Differences between Algorithm and Pseudocode
3.2.4 Problem Case/ Example
3.3 Need of Algorithms
4.0 Conclusion
5.0 Summary
6.0 Tutor Marked Assignments
7.0 Further Reading and Other Resources
1.0 INTRODUCTION
The word algorithm literarily means “a step-by-step procedure used in
solving a problem” and is a type of effective method in which a finite
list of well-defined instructions for completing a task; that given an
initial state, will proceed through a well-defined series of successive
states, eventually terminating in an end-state. The concept of an
algorithm originated as a means of recording procedures for solving
mathematical problems such as finding the common divisor of two
numbers or multiplying two numbers.
2.0 OBJECTIVES
By the end of this unit, you should be able to:
Define and describe what an algorithm is
Enumerate the different characteristics of an algorithm
Examine some of the advantages of algorithms
Identify some shortcomings or disadvantages of algorithms
Look at the the concept of a pseudocode
Examine some benefits and shortcomings of a pseudocode
Make a comparison between and algorithm and a pseudocode
Look at the various reasons why an algorithm is needed
1
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
3.0 WHAT IS AN ALGORITHM?
An algorithm can be defined as a finite set of steps, which has to be
followed while carrying out a particular problem. It is nothing but a
process of executing actions step by step.
An algorithm is a distinct computational procedure that takes input as a
set of values and results in the output as a set of values by solving the
problem. More precisely, an algorithm is correct, if, for each input
instance, it gets the correct output and gets terminated.
An algorithm unravels the computational problems to output the desired
result. An algorithm can be described by incorporating a natural
language such as English, Computer language, or a hardware language.
Algorithms are named after the 9th century Persian mathematician Al-
Khowarizmi. He wrote a treatise in Arabic in 825 AD, On Calculation
with Hindu Numerals. It was translated into Latin in the 12th century as
Algoritmi de numero Indorum, which title was likely intended to mean
"[Book by] Algoritmus on the numbers of the Indians", where
"Algoritmi" was the translator's rendition of the author's name in the
genitive case; but people misunderstanding the title treated Algoritmi as
a Latin plural and this led to the word "algorithm" (Latin algorismus)
coming to mean "calculation method".
3.1 Characteristics of Algorithms
The main Characteristics or features of Algorithms are;
Input: It should externally supply zero or more quantities or data.
Output: It results in at least one quantity or result.
Definiteness: Each instruction should be clear and ambiguous.
Finiteness: An algorithm should terminate after executing a
finite number of steps.
Effectiveness: Every instruction should be fundamental to be
carried out, in principle, by a person using only pen and paper.
Feasible: It must be feasible enough to produce each instruction.
Flexibility: It must be flexible enough to carry out desired
changes with no efforts.
Efficient: The term efficiency is measured in terms of time and
space required by an algorithm to implement. Thus, an algorithm
must ensure that it takes little time and less memory space
meeting the acceptable limit of development time.
Independent: An algorithm must be language independent,
which means that it should mainly focus on the input and the
procedure required to derive the output instead of depending
upon the language.
2
CIT 310 MODULE 1
3.1.1 Advantages of Algorithms
Effective Communication: Since it is written in a natural
language like English, it becomes easy to understand the step-by-
step delineation of a solution to any particular problem.
Easy Debugging: A well-designed algorithm facilitates easy
debugging to detect the logical errors that occurred inside the
program.
Easy and Efficient Coding: An algorithm is nothing but a
blueprint of a program that helps develop a program.
Independent of Programming Language: Since it is a
language-independent, it can be easily coded by incorporating
any high-level language.
3.1.2 Disadvantages of Algorithms
Developing algorithms for complex problems would be time-
consuming and difficult to understand.
It is a challenging task to understand complex logic through
algorithms.
3.2 Pseudocode
Pseudocode refers to an informal high-level description of the operating
principle of a computer program or algorithm. It uses structural
conventions of a standard programming language intended for human
reading rather than the machine reading.
3.2.1 Advantages of Pseudocode
It can be quickly transformed into an actual programming
language than a flowchart since it is similar to a programming
language.
The layman or user can easily understand it.
It can be easily modified as compared to flowcharts.
Its implementation is beneficial for structured, designed elements.
It can easily detect an error before transforming it into a code.
3.2.2 Disadvantages of Pseudocode
Since it does not incorporate any standardized style or format, it
can vary from one user or programmer to another.
Error possibility is higher while transforming into a code.
3
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
It may require a tool for extracting out the Pseudocode and
facilitate the drawing flowcharts.
It does not depict the design.
3.2.3 Difference between Algorithm and Pseudocode
i. An algorithm is simply a problem-solving process, which is used
not only in computer science to write a program but also in our
day to day life. It is nothing but a series of instructions to solve a
problem or get to the problem's solution. It not only helps in
simplifying the problem but also to have a better understanding
of it.
ii. However, Pseudocode is a way of writing an algorithm.
Programmers can use informal, simple language to write
pseudocode without following any strict syntax. It encompasses
semi-mathematical statements.
3.2.4 Problem Case/ Example:
Suppose there are 60 students in a class. How will you calculate
the number of absentees in the class?
i. Pseudocode Approach:
1. Initialize a variable called Count to zero, absent to
zero, total to 60
2. FOR EACH Student PRESENT DO the following:
Increase the Count by One
3. Then Subtract Count from total and store the result
in absent
4. Display the number of absent students
ii. Algorithmic Approach:
1. Count <- 0, absent <- 0, total <- 60
2. REPEAT till all students counted
Count <- Count + 1
3. absent <- total - Count
4. Print "Number absent is:" , absent
3.3 Need of Algorithms (Why do we need Algorithms?)
1. To understand the basic idea of the problem.
2. To find an approach to solve the problem.
3. To improve the efficiency of existing techniques.
4. To understand the basic principles of designing the algorithms.
4
CIT 310 MODULE 1
5. To compare the performance of the algorithm with respect to
other techniques.
6. It is the best method of description without describing the
implementation detail.
7. The Algorithm gives a clear description of requirements and goal
of the problem to the designer.
8. A good design can produce a good solution.
9. To understand the flow of the problem.
10. To measure the behavior (or performance) of the methods in all
cases (best cases, worst cases, average cases)
11. With the help of an algorithm, we can also identify the resources
(memory, input-output) cycles required by the algorithm.
12. With the help of algorithm, we convert art into a science.
13. To understand the principle of designing.
14. We can measure and analyze the complexity (time and space) of
the problems concerning input size without implementing and
running it; it will reduce the cost of design.
Self-Assessment Exercise
1. What is an algorithm?
2. Differentiate between an algorithm and a pseudocode
3. Highlight some of the basic reasons why algorithms are needed?
4. How is an algorithm similar to and different from a program?
5. Why must every good computer programmer understand an
algorithm first?
6. State an algorithm for adding three numbers A, B, and C
4.0 CONCLUSION
The concept of understanding and writing computer algorithms is very
essential to understanding the task of programming and every computing
student has to imbibe the concepts of algorithms. In fact, algorithms are
the basic key to understanding the theory and practice of computing.
5.0 SUMMARY
In this unit we have considered an overview of algorithms and their
basic characteristics. In addition, we looked at some of the benefits and
shortcomings of algorithms and also examined the concept of a
pseudocode as well as some of its benefits and shortcomings. We also
made a brief comparison between a pseudocode and an algorithm and
finally looked at some of the reasons why an algorithm is needed
5
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
6.0 TUTOR MARKED ASSIGNMENT
1. Explain the following terms; (a) Algorithms (b)
Pseudocode
(c) Computer Programs
2. State five properties or features of an algorithm.
3. State some basic differences between an algorithm and a
pseudocode and also between an algorithm and a computer
program
4. Give four benefits each of an algorithm and a pseudocode
7.0 FURTHER READING AND OTHER RESOURCES
Jena, S. R. and Patro, S. (2018) – Design and Analysis of Algorithms,
ISBN 978-93-935274-311-7
Baase, S. and Van Gelder, A. (2008). Computer Algorithms:
Introduction to Design and Analysis, Pearson Education.
6
CIT 310 MODULE 1
MODULE 1 BASIC ALGORITHM ANALYSIS
UNIT 2 ANALYSIS AND COMPLEXITY OF
ALGORITHMS
1.0 Introduction
2.0 Objectives
3.0 Analysis of Algorithms
3.1 Types of Time Complexity Analysis
3.1.1 Worst-case Time Complexity
3.1.2 Average-case Time Complexity
3.1.3 Best-case Time Complexity
3.2 Complexity of Algorithms
3.3 Typical Complexities of an Algorithm
3.3.1 Constant complexity
3.3.2 Logarithmic complexity
3.3.3 Linear complexity
3.3.4 Quadratic complexity
3.3.5 Cubic complexity
3.3.6 Exponential complexity
3.4 How to approximate the Time taken by an Algorithm
3.4.1 Some Examples
4.0 Conclusion
5.0 Summary
6.0 Tutor Marked Assignments
7.0 Further Reading/ References
1.0 INTRODUCTION
Analysis of an algorithm is the same thing as estimating the efficiency
of the algorithm. There are two fundamental parameters based on which
we can analyze the algorithm and they are Space and Time Complexity.
There is also the concept in Time Complexity of estimating the running
time of an algorithm and we have the Best-case, Average-case and
Worst-case
2.0 OBJECTIVES
By the end of this unit, you will be able to
Understand runtime and space analysis or complexity of
algorithms
Know the different types of analysis
Understand the typical complexities of an algorithm
Learn how to approximate the time taken by an algorithm
7
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
3.0 Analysis of Algorithm
The analysis is a process of estimating the efficiency of an algorithm
and that is, trying to know how good or how bad an algorithm could be.
There are two main parameters based on which we can analyze the
algorithm:
Space Complexity: The space complexity can be understood as
the amount of space required by an algorithm to run to
completion.
Time Complexity: Time complexity is a function of input
size n that refers to the amount of time needed by an algorithm to
run to completion.
Let's understand it with an example.
Suppose there is a problem to solve in Computer Science, and in
general, we solve a problem by writing a program. If you want to write a
program in some programming language like C, then before writing a
program, it is necessary to write a blueprint in an informal language.
Or in other words, you should describe what you want to include in your
code in an English-like language for it to be more readable and
understandable before implementing it, which is nothing but the concept
of Algorithm.
In general, if there is a problem P1, then it may have many solutions,
such that each of these solutions is regarded as an algorithm. So, there
may be many algorithms such as A1, A2, A3, …, An.
Before you implement any algorithm as a program, it is better to find out
which among these algorithms are good in terms of time and memory.
It would be best to analyze every algorithm in terms of Time that relates
to which one could execute faster and Memory or Space corresponding
to which one will take less memory.
So, the Design and Analysis of Algorithm talks about how to design
various algorithms and how to analyze them. After designing and
analyzing, choose the best algorithm that takes the least time and the
least memory and then implement it as a program in C or any preferable
language.
We will be looking more on time rather than space because time is
instead a more limiting parameter in terms of the hardware. It is not easy
to take a computer and change its speed. So, if we are running an
algorithm on a particular platform, we are more or less stuck with the
performance that platform can give us in terms of speed.
8
CIT 310 MODULE 1
However, on the other hand, memory is relatively more flexible. We can
increase the memory as when required by simply adding a memory card.
So, we will focus on time than that of the space.
The running time is measured in terms of a particular piece of hardware,
not a robust measure. When we run the same algorithm on a different
computer which might be faster or use different programming languages
which may be designed to compile faster, we will find out that the same
algorithm takes a different time.
3.1 Types of Time Complexity Analysis
We have three types of analysis related to time complexity, which are:
3.1.1 Worst-case time complexity: For 'n' input size, the worst-case
time complexity can be defined as the maximum amount of time
needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the maximum number of steps
performed on an instance having an input size of n. Computer
Scientists are more interested in this.
3.1.2 Average case time complexity: For 'n' input size, the average-
case time complexity can be defined as the average amount of
time needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the average number of steps
performed on an instance having an input size of n.
3.1.3 Best case time complexity: For 'n' input size, the best-case time
complexity can be defined as the minimum amount of time
needed by an algorithm to complete its execution. Thus, it is
nothing but a function defined by the minimum number of steps
performed on an instance having an input size of n.
3.2 Complexity of Algorithms
The term algorithm complexity measures how many steps are required
by the algorithm to solve the given problem. It evaluates the order of
count of operations executed by an algorithm as a function of input data
size.
To assess the complexity, the order (approximation) of the count of
operation is always considered instead of counting the exact steps.
O(f) notation represents the complexity of an algorithm, which is also
termed as an Asymptotic notation or "Big O" notation. Here the f
corresponds to the function whose size is the same as that of the input
9
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
data. The complexity of the asymptotic computation O(f) determines in
which order the resources such as CPU time, memory, etc. are
consumed by the algorithm that is articulated as a function of the size of
the input data.
The complexity can be found in any form such as constant, logarithmic,
linear, n*log(n), quadratic, cubic, exponential, etc. It is nothing but the
order of constant, logarithmic, linear and so on, the number of steps
encountered for the completion of a particular algorithm. To make it
even more precise, we often call the complexity of an algorithm as
"running time".
3.3 Typical Complexities of an Algorithm
We take a look at the different types of complexities of an algorithm and
one or more of our algorithm or program will fall into any of the
following categories;
3.3.1 Constant Complexity
Imposes a complexity of O (1). It undergoes an execution of a constant
number of steps like 1, 5, 10, etc. for solving a given problem. The count
of operations is independent of the input data size.
3.3.2 Logarithmic Complexity
Imposes a complexity of O (log(N)). It undergoes the execution of the
order of log (N) steps. To perform operations on N elements, it often
takes the logarithmic base as 2.
For N = 1,000,000, an algorithm that has a complexity of O(log(N))
would undergo 20 steps (with a constant precision). Here, the
logarithmic base does not hold a necessary consequence for the
operation count order, so it is usually omitted.
3.3.3 Linear Complexity
Imposes a complexity of O (N). It encompasses the same number of
steps as that of the total number of elements to implement an operation
on N elements.
For example, if there exist 500 elements, then it will take about 500
steps. Basically, in linear complexity, the number of elements linearly
depends on the number of steps. For example, the number of steps for N
elements can be N/2 or 3*N.
10
CIT 310 MODULE 1
It also imposes a run time of O(n*log(n)). It undergoes the
execution of the order N*log(N) on N number of elements to
solve the given problem.
For a given 1000 elements, the linear complexity will execute
10,000 steps for solving a given problem.
3.3.4 Quadratic Complexity
It imposes a complexity of O (n2). For N input data size, it undergoes
the order of N2 count of operations on N number of elements for solving
a given problem.
If N = 100, it will endure 10,000 steps. In other words, whenever the
order of operation tends to have a quadratic relation with the input data
size, it results in quadratic complexity.
For example, for N number of elements, the steps are found to be in the
order of 3*N2/2.
3.3.5 Cubic Complexity
It imposes a complexity of O (n3). For N input data size, it executes the
order of N3 steps on N elements to solve a given problem.
For example, if there exist 100 elements, it is going to execute 1,000,000
steps.
3.3.6 Exponential Complexity
It imposes a complexity of O(2n), O(N!), O(nk), …. For N elements, it
will execute the order of count of operations that is exponentially
dependable on the input data size.
For example, if N = 10, then the exponential function 2N will result in
1024. Similarly, if N = 20, it will result in 1048 576, and if N = 100, it
will result in a number having 30 digits.
The exponential function N! grows even faster; for example, if N = 5
will result in 120. Likewise, if N = 10, it will result in 3,628,800 and so
on.
Since the constants do not hold a significant effect on the order of count
of operation, so it is better to ignore them.
11
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
Thus, to consider an algorithm to be linear and equally efficient, it must
undergo N, N/2 or 3*N count of operation, respectively, on the same
number of elements to solve a particular problem
A summary of these complexities is given below:
Self Assessment Exercises
1. Compare the Worst-case and the Best-case analysis of an
algorithm
2. Why is the Worst-case analysis the most important in algorithm
analysis?
3. Among the different complexity types of an algorithm, which do
you consider as the worst?
4. Presently we can solve problem instances of size 30 in 1 minute
using algorithm A, which is a Θ(2n) algorithm. On the other
hand, we will soon have to solve problem instances twice this
large in 1 minute. Do you think it would help to buy a faster (and
more expensive) computer?
3.4 How to approximate the time taken by the Algorithm?
So, to find it out, we shall first understand the types of the algorithm we
have. There are two types of algorithms:
1. Iterative Algorithm: In the iterative approach, the function
repeatedly runs until the condition is met or it fails. It involves
the looping construct.
2. Recursive Algorithm: In the recursive approach, the function
calls itself until the condition is met. It integrates the branching
structure.
12
CIT 310 MODULE 1
However, it is worth noting that any program that is written in iteration
could be written as recursion. Likewise, a recursive program can be
converted to iteration, making both of these algorithms equivalent to
each other.
But to analyze the iterative program, we have to count the number of
times the loop is going to execute, whereas in the recursive program, we
use recursive equations, i.e., we write a function of F(n) in terms of
F(n/2).
Suppose the program is neither iterative nor recursive. In that case, it
can be concluded that there is no dependency of the running time on the
input data size, i.e., whatever is the input size, the running time is going
to be a constant value. Thus, for such programs, the complexity will
be O(1).
3.4.1 Some Examples to Consider
a. For Iterative Programs
Consider the following programs written in simple English and does not
correspond to any syntax.
Example1
In the first example, we have an integer i and a for loop running from i
equals 1 to n. Now the question arises, how many times does the name
get printed?
A()
{
int i;
for (i=1 to n)
printf("Abdullahi");
}
Since i equals 1 to n, so the above program will print Abdullahi, n
number of times. Thus, the complexity will be O(n).
Example2:
A()
{
int i, j:
for (i=1 to n)
for (j=1 to n)
printf("Abdullahi");
}
13
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
In this case, firstly, the outer loop will run n times, such that for each
time, the inner loop will also run n times. Thus, the time complexity will
be O(n2).
Example3:
A()
{
i = 1; S = 1;
while (S<=n)
{
i++;
SS = S + i;
printf("Abdullahi");
}
}
As we can see from the above example, we have two variables; i, S and
then we have while S<=n, which means S will start at 1, and the entire
loop will stop whenever S value reaches a point where S becomes
greater than n.
Here i is incrementing in steps of one, and S will increment by the value
of i, i.e., the increment in i is linear. However, the increment in S
depends on the i.
Initially;
i=1, S=1
After 1st iteration;
i=2, S=3
After 2nd iteration;
i=3, S=6
After 3rd iteration;
i=4, S=10 … and so on.
Since we don't know the value of n, so let's suppose it to be k. Now, if
we notice the value of S in the above case is increasing; for i=1, S=1;
i=2, S=3; i=3, S=6; i=4, S=10; …
Thus, it is nothing but a series of the sum of first n natural numbers, i.e.,
𝑘 (𝑘+1)
by the time i reaches k, the value of S will be .
2
𝑘 (𝑘+1)
To stop the loop, has to be greater than n, and when we solve
2
this equation,
14
CIT 310 MODULE 1
we will get > n.
Hence, it can be concluded that we get a complexity of O(√n) in this
case.
b. For Recursive Program
Consider the following recursive programs.
Example1
A(n)
{
if (n>1)
return (A(n-1))
}
Solution;
Here we will see the simple Back Substitution method to solve the
above problem.
T(n) = 1 + T(n-1) … Eqn. (1)
Step1: Substitute n-1 at the place of n in Eqn. (1)
T(n-1) = 1 + T(n-2) .. .Eqn. (2)
Step2: Substitute n-2 at the place of n in Eqn. (1)
T(n-2) = 1 + T(n-3) … Eqn. (3)
Step3: Substitute Eqn. (2) in Eqn. (1)
T(n)= 1 + 1+ T(n-2) = 2 + T(n-2) … Eqn. (4)
Step4: Substitute eqn. (3) in Eqn. (4)
T(n) = 2 + 1 + T(n-3) = 3 + T(n-3) = …... = k + T(n-k) …Eqn. (5)
Now, according to Eqn. (1), i.e. T(n) = 1 + T(n-1), the algorithm will run
until n>1. Basically, n will start from a very large number, and it will
decrease gradually. So, when T(n) = 1, the algorithm eventually stops,
and such a terminating condition is called anchor condition, base
condition or stopping condition.
15
CIT 310 ALGORITHMS AND COMPLEXITY ANALYSIS
Thus, for k = n-1, the T(n) will become.
Step5: Substitute k = n-1 in eqn. (5)
T(n) = (n-1) + T(n-(n-1)) = (n-1) + T(1) = n-1+1
Hence, T(n) = n or O(n).
4.0 CONCLUSION
Analysis of algorithms helps us to determine how good or how bad they
are in terms of speed or time taken and memory or space utilized.
Designing good programs is dependent on how good or how bad the
algorithm is and the analysis helps us to determine the efficiency of such
algorithms.
5.0 SUMMARY
In the unit, we have learnt the meaning of algorithm analysis and the
different types of analysis. We also examined the complexity of
algorithms and the different types of complexities.
6.0 TUTOR MARKED ASSIGNMENT
1. Between the Worst-case and the Best-case analysis, which is
more important to a computer programmer and why?.
2. Why must we avoid exponential complexity at all costs?
3. What do we gain by the analysis of algorithms?
4. Assuming you have a computer that requires 1 minute to solve
problem instances of size n = 1,000. Suppose you buy a new
computer that runs 1,000 times faster than the old one. What
instance sizes can be run in 1 minute, assuming the following
time complexities T(n) for our algorithm?
(a) T(n) = n (b) T(n) = n3 (c) T(n) = 10n
7.0 FURTHER READING AND OTHER RESOURCES
Berman, K.A. and Paul, J.L.(2005). Algorithms: Sequential, Parallel,
and Distributed. Course Technology.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009).
Introduction to Algorithms, 3rd ed. MIT Press.
Jena, S. R. and Patro, S. (2018) – Design and Analysis of Algorithms,
ISBN 978-93-935274-311-7
16