UNIT- I

Notion of an Algorithm
The algorithm is a collection of unambiguous (clear) instructions occurring in some specific
sequence and it should produce an output for given set of input in finite amount of time.

The notion of an algorithm is a finite sequence of unambiguous instructions for solving a

problem which takes a input and produces a required output in a finite amount of time.

Problem

Algorithm

Program

Input Computer Output

In addition every algorithm must satisfy the following criteria:

Input: there are zero or more quantities, which are externally supplied as input

Output: at least one quantity is produced as a result

Definiteness: each instruction must be clear and unambiguous

Finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm
will terminate after a finite number of steps

Effectiveness: every instruction must be sufficiently basic that it can be carried out by a
person using only pencil and paper. It is not enough that each operation be definite, but it
must also be feasible (possible).

An algorithm can be represented using a pseudo language that is a combination of the

programming language together with informal English statements.

Pseudocode: Algorithm can be represented in text mode and graphic mode. The graphical
representation of an algorithm is called Flowchart. While the text mode (Pseudocode) is

1
an informal, high-level description of a computer program or algorithm intended for
human reading rather than machine execution.

In other words, a Pseudocode is:

 High-level description of an algorithm.

 More structured than plain English.
 Less detailed than a program.
 Preferred notation for describing algorithms.
 Hides program design issues.

Properties of an Algorithm:

1. Non ambiguity: Each step in an algorithm should be non- ambiguous. It means each
instruction should be clear & precise. It indicates effectiveness of algorithm.
2. Range of input: It must be specified otherwise the algorithm can go in an infinite
state.
3. Multiplicity: The same algorithm can be represented in several different ways.
4. Speed: Algorithm must be efficient & should produce output with fast speed.
5. Finiteness: The algorithm should be finite. It means after performing required
operations is should terminate.

Algorithm to count the sum of n numbers:

sum (1,n)

// Problem Description: It finds the sum of given n numbers

//Input: 1 to n numbers

//Output: The sum of n numbers

result<- 0 (Assigning a value)

for I 1 to n do i+1

result <- result+i

return result

Algorithm to fid if a given number is even or odd:

even_odd (val)

//Problem Description: It checks whether a given number is even or odd

2
 //Input: The number to be tested i.e. val

//Output: A given number is even or odd

If (val %2==0) then

Write (“Number is Even”)

Else

Write (“Number is Odd”)

Algorithm to find the factorial of a number:

fact (n)

//Problem: To find the factorial of a number

//Input: The number n of which factorial is to be calculated

//Output: Factorial of a number

if(n<- 1) then

return 1

Else

return n* fact(n-1)

Fundamentals of Algorithmic Problem Solving:

1. Understanding the problem.

2. Decision making
 Capabilities of computational devices: It is to decide whether the
algorithm to be designed is sequential or parallel.
The sequential algorithm runs on machine that executes instructions
sequentially, while parallel algorithm runs on machine that executes parallel
instructions.
 Exact or Approximate problem solving method: If the problem needs to
be solved correctly then, exact problem solving method is used. When the
problem is complex and exact solution won’t be possible then approximate
algorithm is used.

3
 Data Structure: A specialized format for organizing, storing and accessing
data in a computer’s memory so it can be used efficiently.

Data Structure

Non-
Primitive
Primitive

Float/ Non-
Integer Character Boolean Pointer Linear
Double Linear

Linked
Array Stack Queue Tree Graph
List

Linear Data Structure: Elements are arranged sequentially with each

element connected to previous & next node such as array, linked list, stack
and queue.

Non- Linear Data Structure: Elements are arranged in non linear,

hierarchical formats such as trees, graphs etc.

 Algorithm Design Techniques: It is a general approach by which many

problems can be solved algorithmically.

1. Brute Force Design: The most straightforward method, which try out
all possible solutions to find out one that works. It is simple but
inefficient for large problems.
2. Divide & Conquer Design: It breaks the problem into smaller
independent sub- problems of same nature, solves these sub problems
recursively and then combines their solutions to get overall solution.
3. Dynamic Programming: It solves complex problems by breaking
them down into simpler overlapping sub problems. [Overlapping sub
problem refers to a situation where a problem can be broken into

4
 smaller sub problems and these same sub problems are solved
multiple times during recursive process].
Example: Fibonacci Series: To find F(5), we call F(4), F(3), F(2) and
F(1).
4. Greedy Approach: It builds a solution step- by- step by always
making the locally optimal choice at each stage, with the hope that
these local decisions will lead to a globally optimal solution. Example:
The Coin Change Problem.
5. Backtracking: It builds a solution incrementally & backtracks (goes
back) as soon as it finds that the current path cannot lead to a valid
solution. Example: Crossword.
It is considered as refined Brute force algorithm, as in Brute Force
every possible solution is checked, backtracking also uses pruning to
leave invalid paths. [Pruning: A technique used to reduce the size of a
search space by cutting off branches that are found to be irrelevant.]
6. Decrease & Conquer: It reduces a problem instance into a smaller or
simpler instance of same problem, solves the smaller instance & then
extends the solution to original instance. Example: Searching a
dictionary.
7. Transform & Conquer: It works by transforming the problem into a
different form. Consider a list of 100 random numbers and you have
to find are there any duplicates. [5,3,5,1]
Direct attack: You pick the first number and compare it to other 99
numbers. Then you pick second number & compare it to remaining 98
& so on.
Transform & Conquer: First transform the above list in ascending
order. [1, 3, 5, 5]
Second step is to conquer (traverse) this list and find are there any
duplicates present or not.
 Design an algorithm:

Algorithm

Using Natural Pseudocode Flowchart

Language

5
 Using Natural Language: Any language that has evolved through human use
for communication.
 Pseudocode: It is a combination of natural language & programming
language construct. It is more precise than a natural language.
 Flowchart: It is a graphical representation of an algorithm.

Name Symbol Purpose

Terminal Start/stop/begin/end

Input/output Input/output of data

Process Any processing to be

performed can be
represented

Decision box Decision operations that

determine which of the
alternative paths to be
followed

Connector Used to connect different

parts of flowchart

Arrows Joins 2 symbols and also

represents flow of
execution

Pre defined process Modules (or)subroutines

specified else where

For loop symbol Shows initialization,

condition and
incrimination of loop
variable.

6
Example: Flowchart of addition of two numbers:

 Prove correctness of an algorithm: An algorithm is proved correct by

mathematical induction/ reasoning that particular will always produces
intended result for valid input.
 Analysis of algorithm: The analysis of a program is the amount of computer
memory and time needed to run a program.

1. Time Complexity: The time needed by an algorithm expressed as a function

of the size (n) of a problem is called the time complexity of the algorithm. It is
the amount of computer time it needs to run to completion.
In other words, amount of time taken by the algorithm to run. It tells the
algorithm is slow or fast.
The limiting behavior of the complexity as size increases is called the
asymptotic time complexity. It is the asymptotic complexity of an algorithm,
which ultimately determines the size of problems that can be solved by the
algorithm.
2. Space Complexity: The amount of space / memory taken by a program to
execute.

7
Space Complexity: It is a measure of amount of RAM an algorithm needs to run to
completion, relative to the size of the input. It also finds how much extra space the
algorithm creates to get the job done.

Instruction space: Instruction space is the space needed to store the compiled version of
the program instructions.

Data space: Data space is the space needed to store all constant and variable values. It has
two components:

 Space needed by constants and simple variables in program.

 Space needed by dynamically allocated objects such as arrays and class instances.

Environment stack space: The environment stack is used to save information needed to
resume execution of partially completed functions.

Total space used by an algorithm is sum of:

1. Input Space: The memory required to store the input data itself.
2. Auxiliary space: The extra/ temporary space used by an algorithm (local variables,
recursion stacks, temporary arrays etc.).

S (p) = C + Sp

C: Constant, that denotes the space of inputs and outputs.

This space is an amount of space taken by instruction, variables and identifiers.

Sp: It is a variable part whose space requirement depends on particular problem instance.

Time Complexity: It is a measure of how the execution time of an algorithm changes

relative to the size of input data. In other words, time complexity of an algorithm is the
amount of computer time required by an algorithm to run to completion.

In multiuser system, execution time depends on –

 System load
 Number of other programs running
 Instruction set used
 Speed of hardware

Time complexity is given in terms of frequency count [it is a count denoting number of
times a statement is executed].

8
Classification of algorithms (On the basis of Time Complexity):

Example 1: O (1) Constant Time Complexity

void main ()
Time
{

int a=10, b=90, c;

c=a + b;

printf ( “%d”, c);

Input size
}

Statement Frequency Count

int a, b, c 1
c=a+b 1
printf (“%d”, c) 1
Total 3

Algorithm is O (3), here 3 is a constant number. So the time complexity is Constant.

Next instructions of most programs are executed once or at most only a few times. If all the
instructions of a program have this property, we say that its running time is a constant.

A flat horizontal line is drawn when a statement is executed only once. No matter how
much data is added, time stays same (no extra memory is needed regardless of input size).

Example 2: O (n) Linear Time Complexity

for (i=0; i<n; i++)

Sum=sum+a[i];

Statement Frequency Count

i=0 1
i<n It executes n+1 times
i++ n times
sum=sum + a[i] n times
Total 3n+2

9
When the running time of a program is linear, it is generally the case that a small amount of
processing is done on each input element. This is the optimal situation for an algorithm
that must process n inputs.

Example 3: O (n2) Quadratic Time Complexity

for (i=0; i<n; i++)

for (j=0; j<n; j++)

C[i][j]= a[i][j]+b[i][j];

Statement Frequency Count

i=0 1
i<n n+1
i++ n
j=0 n
j<n n*(n+1)
j++ n*n
C[i][j]= a[i][j]+b[i][j] n*n
Total 3n +4n+2
2

When the running time of an algorithm is quadratic, it is practical for use only on relatively
small problems. Quadratic running times typically arise in algorithms that process all pairs
of data items (perhaps in a double nested loop) whenever n doubles, the running time
increases four fold.

Example 4: O (n3) Cubic Time Complexity

for (i=0; i<n; i++)

for (j=0; j<n; j++)

for (k=0; k< n; k++)

10
 {

C[i][j]= c[i][j]+ a[i][k]* b[k][j];

Statement Frequency Count

i=0 1
i<n n+1
i++ n
j=0 n
j<n n*(n+1)
j++ n*n
k=0 n*n
k<n n*n*(n+1)
k++ n*n*n
C[i][j]= c[i][j]+ a[i][k]* b[k][j] n*n*n
Total 3n3+4n2+4n+2

Algorithm is O (n3) [Cubic Time Complexity] and so on.

An algorithm that process triples of data items (perhaps in a triple–nested loop) has a cubic
running time and is practical for use only on small problems. Whenever n doubles, the
running time increases simultaneously.

Note: Quadratic complexity: The curve grows quickly, shaped like a parabola.

Cubic complexity: The curve rises much more steeply (means how fast the line on the
graph moves upward) and rapidly than the quadratic curve, becomes almost vertical as n
increases, which signifies low efficiency.

Example 5: O (log n) Logarithmic Time Complexity

It is calculated got algorithm that solves problems repeatedly dividing the input size by a
constant factor (usually 2).

It means the number of steps required to finish the task grows very slowly as input size ‘n’
increases. Here an algorithm reduces search space by half in every step.

11
 n

n/2 n/2

n/4 n/4 n/4 n/4

n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

1 1 1 1 1 1 1 1

To find how many steps (k) it takes to reach 1,

𝒏
=𝟏
𝟐𝒌

This represents dividing the original n by 2, exactly k times to get down to a single
remaining item.

Multiply both sides by 2k.

𝒏
𝟐𝒌 ∗ = 𝟐𝒌 ∗ 𝟏
𝟐𝒌

𝒏 = 𝟐𝒌

Now take logarithm (base 2) of both sides,

𝐥𝐨𝐠 𝟐 𝒏 = 𝐥𝐨𝐠 𝟐 𝟐𝒌

Since, 𝐥𝐨𝐠 𝟐 𝟐𝒌 = 𝒌

𝒌 = 𝐥𝐨𝐠 𝟐 𝒏

Therefore, the number of operations k is directly proportional to (log 𝑛) . A logarithmic

curve rises quickly at first and then flattens.

12
When the running time of a program is logarithmic, the program gets slightly slower as n
grows. This running time commonly occurs in programs that solve a big problem by
transforming it into a smaller.

Example 5: O (n*log n) Linearithmic Time Complexity

It occurs when an algorithm performs a linear amount of work O (n) at every level of a
process that repeatedly divides the problem size. It is used in Merge Sort.

1. The log (n) part (number of levels): This is obtained by repeatedly dividing the
input space in half.

n/2 n/2

n/4 n/4 n/4 n/4

n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

1 1 1 1 1 1 1 1

2. ‘n’ part (work per level): At each of these log n levels, the algorithm must process
every element once to recombine or sort. For example, in merge sort each level
involves merging sub arrays until all n elements together to obtain the sorted array.

This running time arises for algorithms that solve a problem by breaking it up into smaller
sub-problems, solving then independently and then combining the solutions. When ‘n’
doubles, running time will be more than double.

Example 6: O (2n) Exponential Time Complexity: It means the execution time of an

algorithm doubles every single addition to the input size n.

This complexity arises when an algorithm must explore all possible combinations of a data
set. To calculate this complexity recurrence relation is used.

Ex: Fibonacci series.

13
Order of Growth:

Measuring the performance of an algorithm in relation with the input size n is called order
of growth.

The standard order of growth from slowest growing (most efficient) to fastest growing
(least efficient) is as follows:

O (1) < O (log n) < O (n) < O (n* log n) < O (n 2) < O (n3) < O (nk) < O (2n) < O (n!)

Asymptotic Notation
Asymptotic notation is a mathematical language used to describe
the efficiency and performance of algorithms. It focuses on how an algorithm's resource
requirements (time or space) grow as the input size (n) approaches infinity.

These notations provide a concise way to express the behavior of an algorithm's time or
space complexity as the input size approaches infinity. Rather than comparing algorithms
directly, asymptotic analysis focuses on understanding the relative growth rates of
algorithms' complexities. It enables comparisons of algorithms' efficiency by removing
machine-specific constants and implementation details.

Asymptotic analysis allows for the comparison of algorithms' space and time complexities
by examining their performance characteristics as the input size varies. By using these
notations, such as Big O, Big Omega, and Big Theta, algorithms can be categorized as
Worst-case, Best-case or Average-case time or space complexities.

There are mainly three asymptotic notations:

1. Big-O Notation (O-notation): It represents upper bound of algorithm’s running

time. Using this, the longest amount of time taken by an algorithm to complete is
specified.

14
 In other words, it is a worst case scenario where an algorithm will never be slower
than this.

Let f(n) and g(n) be two non- negative functions (they always produces values
greater than or equal to zero for all valid inputs.)

Let n0 and constant ‘C’ are two integers, such n0≥k [k≥0] and C≥0.

𝒇(𝒏) ≤ 𝑪 ∗ 𝒈(𝒏)

f (n): The actual runtime or space used by an algorithm.

g (n): The growth rate function against which f (n) is compared.

𝒇(𝒏) ∈ 𝑶(𝒈(𝒏))

In other words, f (n) is less than g (n) if g (n) is multiple of some constant ‘c’.

Ex: Total time required to complete an algorithm is

𝑓(𝑛 ) = 2𝑛 2 + 𝑛

𝑓 (𝑛 ) = 𝑂()

2𝑛 2 + 𝑛 ≤ 𝑐 ∗ 𝑔(𝑛 2 )

Here n2 is considered as the least upper bound from 2n2+n.

Let C=2

2𝑛 2 + 𝑛 ≤ 2 ∗ 𝑛 2

Let C=3

2𝑛 2 + 𝑛 ≤ 3 ∗ 𝑛 2

𝒏 ≤ 𝒏𝟐

For all values of n

Here before n0 the value of f (n) may fluctuate but after n 0 f (n) will always be less than g
(n).

15
 C * g (n)
t

f (n)

N0 n

Worst Case

Upper bound (At most)

2. Big Omega Notation (Ω-notation): It is used to represent lower bound of

algorithm running time. It denotes the shortest amount of time taken by an
algorithm.

A function f (n) is said to be Ω (𝑔 (𝑛)) if f (n) is bounded below some positive

constant multiple of g (n) such that:

𝒇 (𝒏) ≥ 𝑪 ∗ 𝒈 (𝒏)

𝒇(𝒏) ∈ Ω(𝒈(𝒏))

f (n)
t

Best Case
C * g (n)
Lower Bound

(Atleast Case)

N0 n

16
 Let, 𝑓(𝑛 ) = 2𝑛 2 + 𝑛

2𝑛 2 + 𝑛 ≥ 𝑐 ∗ 𝑔(𝑛)

Now g (n) should be selected as the greatest lower bound.

2𝑛 2 + 𝑛 ≥ 𝑐 ∗ 𝑛 2

Let c=2

2𝑛 2 + 𝑛 ≥ 2 ∗ 𝑛 2

𝒏≥𝟎

3. Theta Notation (Θ-notation): It denotes the running time between upper bound
and lower bound. Let f (n) and g (n) are two non- negative functions. There are two
positive constants c1 and c2.

𝑪𝟏 ∗ 𝒈(𝒏) ≤ 𝒇(𝒏) ≤ 𝑪𝟐 ∗ 𝒈(𝒏)

𝒇(𝒏) ∈ 𝜽 (𝒈(𝒏) )

t C2 * g (n)

f (n)

Average Case

Exact Time C1 * g (n)

Let 𝑓(𝑛 ) = 2𝑛 2 + 𝑛

𝑐1 ∗ 𝑔(𝑛 ) ≤ 2𝑛 2 + 𝑛 ≤ 𝑐2 ∗ 𝑔(𝑛)

𝑐1 ∗ 𝑛 2 ≤ 2𝑛 2 + 𝑛 ≤ 𝑐2 ∗ 𝑛 2

Let c1=2 and c2=3 2 ∗ 𝑛 2 ≤ 2𝑛 2 + 𝑛 ≤ 3 ∗ 𝑛 2

17
Best Case: The minimum possible value of f (n) is called the best case.

Average Case: The expected value of f (n).

Worst Case: The maximum value of f (n) for any key possible input.

Big Oh is mostly used, because it tells maximum time an algorithm requires completing its
execution, which will cover all three best, average and worst cases.

4. Little o: Little o notation is used to describe an upper bound that cannot be tight. In
other words, loose upper bound of f (n).

𝒇(𝒏) < 𝐶 ∗ 𝑔(𝑛)

5. Little 𝝎: Little omega (ω) notation is used to describe a loose lower bound of f (n).

𝒇(𝒏) > 𝐶 ∗ 𝑔(𝑛)

Properties of Asymptotic Notations:

Notation Reflexive Symmetric Transitive

Big- Oh a≤ 𝒃 YES NO YES
Big Omega a≥ 𝒃 YES NO YES
Theta a=b YES YES YES
Little o a>b NO NO YES
Little 𝜔 a<b NO NO YES
Reflexive: The reflexive property of equality is applied to the set of numbers which states
that every number is equal to itself. (A=A)

Symmetric: If one element in a set is related to the other, then we can say that the second
element is also related to the first element. (A>B then B>A or A<B then B<A)

Transitive: If A, B, and C are three quantities, and if A is related to B by some rule and B is
related to C by the same rule, then A and C are related to each other by the same rule, this
property is called transitive property of equality. (A≤B, B≤C then A≤C or A≥ 𝐵, B ≥
C then ≥ C )

18