1

Module I : Algorithm Analysis: Algorithm, Properties of a good

algorithm, efficiency considerations, Complexity: Time and Space
complexity, Asymptotic notations: Big O notations, best case, worst case,
average case, simple examples, recursion and its elimination- recursive
and no-recursive algorithms for binary search.

What is an Algorithm?
An algorithm is a process or a set of rules required to perform calculations or some other problem-
solving operations especially by a computer. The formal definition of an algorithm is that it
contains the finite set of instructions which are being carried in a specific order to perform the
specific task. It is not the complete program or code; it is just a solution (logic) of a problem, which
can be represented either as an informal description using a Flowchart or Pseudocode.

Characteristics of an Algorithm

o Input: An algorithm has some input values. We can pass 0 or some input value to an
algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the instructions in
an algorithm should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the algorithm
should contain a limited number of instructions, i.e., the instructions should be countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm affects
the overall process.
o Language independent: An algorithm must be language-independent so that the
instructions in an algorithm can be implemented in any of the languages with the same
output.

Why do we need Algorithms?

We need algorithms because of the following reasons:

o Scalability: It helps us to understand the scalability. When we have a big real-world

problem, we need to scale it down into small-small steps to easily analyze the problem.

JJ@MGCP
 2

o Performance: The real-world is not easily broken down into smaller steps. If the problem
can be easily broken into smaller steps means that the problem is feasible.

Factors of an Algorithm

The following are the factors that we need to consider for designing an algorithm:

o Modularity: If any problem is given and we can break that problem into small-small
modules or small-small steps, which is a basic definition of an algorithm, it means that this
feature has been perfectly designed for the algorithm.
o Correctness: The correctness of an algorithm is defined as when the given inputs produce
the desired output, which means that the algorithm has been designed algorithm. The
analysis of an algorithm has been done correctly.
o Maintainability: Here, maintainability means that the algorithm should be designed in a
very simple structured way so that when we redefine the algorithm, no major change will
be done in the algorithm.
o Functionality: It considers various logical steps to solve the real-world problem.
o Robustness: Robustness means that how an algorithm can clearly define our problem.
o User-friendly: If the algorithm is not user-friendly, then the designer will not be able to
explain it to the programmer.
o Simplicity: If the algorithm is simple then it is easy to understand.
o Extensibility: If any other algorithm designer or programmer wants to use your algorithm
then it should be extensible.

Importance of Algorithms

1. Theoretical importance: When any real-world problem is given to us and we break the
problem into small-small modules. To break down the problem, we should know all the
theoretical aspects.
2. Practical importance: As we know that theory cannot be completed without the practical
implementation. So, the importance of algorithm can be considered as both theoretical and
practical.

Issues of Algorithms

The following are the issues that come while designing an algorithm:
JJ@MGCP
 3

o How to design algorithms: As we know that an algorithm is a step-by-step procedure so

we must follow some steps to design an algorithm.
o How to analyze algorithm efficiency

Approaches of Algorithm

The following are the approaches used after considering both the theoretical and practical
importance of designing an algorithm:

o Brute force algorithm: The general logic structure is applied to design an algorithm. It is
also known as an exhaustive search algorithm that searches all the possibilities to provide
the required solution. Such algorithms are of two types:
1. Optimizing: Finding all the solutions of a problem and then take out the best
solution or if the value of the best solution is known then it will terminate if the best
solution is known.
2. Sacrificing: As soon as the best solution is found, then it will stop.
o Divide and conquer: It is a very implementation of an algorithm. It allows you to design
an algorithm in a step-by-step variation. It breaks down the algorithm to solve the problem
in different methods. It allows you to break down the problem into different methods, and
valid output is produced for the valid input. This valid output is passed to some other
function.
o Greedy algorithm: It is an algorithm paradigm that makes an optimal choice on each
iteration with the hope of getting the best solution. It is easy to implement and has a faster
execution time. But, there are very rare cases in which it provides the optimal solution.
o Dynamic programming: It makes the algorithm more efficient by storing the intermediate
results. It follows five different steps to find the optimal solution for the problem:
1. It breaks down the problem into a subproblem to find the optimal solution.
2. After breaking down the problem, it finds the optimal solution out of these
subproblems.
3. Stores the result of the subproblems is known as memorization.
4. Reuse the result so that it cannot be recomputed for the same subproblems.
5. Finally, it computes the result of the complex program.

JJ@MGCP
 4

o Branch and Bound Algorithm: The branch and bound algorithm can be applied to only
integer programming problems. This approach divides all the sets of feasible solutions into
smaller subsets. These subsets are further evaluated to find the best solution.
o Randomized Algorithm: As we have seen in a regular algorithm, we have predefined
input and required output. Those algorithms that have some defined set of inputs and
required output, and follow some described steps are known as deterministic algorithms.
What happens that when the random variable is introduced in the randomized algorithm?.
In a randomized algorithm, some random bits are introduced by the algorithm and added
in the input to produce the output, which is random in nature. Randomized algorithms are
simpler and efficient than the deterministic algorithm.
o Backtracking: Backtracking is an algorithmic technique that solves the problem
recursively and removes the solution if it does not satisfy the constraints of a problem.

Algorithm Complexity

The performance of the algorithm can be measured in two factors:

o Time complexity: The time complexity of an algorithm is the amount of time required to
complete the execution. The time complexity of an algorithm is denoted by the big O
notation. Here, big O notation is the asymptotic notation to represent the time complexity.
The time complexity is mainly calculated by counting the number of steps to finish the
execution. Let's understand the time complexity through an example.

1. sum=0;
2. // Suppose we have to calculate the sum of n numbers.
3. for i=1 to n
4. sum=sum+i;
5. // when the loop ends then sum holds the sum of the n numbers
6. return sum;

In the above code, the time complexity of the loop statement will be atleast n, and if the value of
n increases, then the time complexity also increases. While the complexity of the code, i.e., return
sum will be constant as its value is not dependent on the value of n and will provide the result in
one step only. We generally consider the worst-time complexity as it is the maximum time taken
for any given input size.

JJ@MGCP
 5

o Space complexity: An algorithm's space complexity is the amount of space required to

solve a problem and produce an output. Similar to the time complexity, space complexity
is also expressed in big O notation.

For an algorithm, the space is required for the following purposes:

1. To store program instructions

2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

Auxiliary space: The extra space required by the algorithm, excluding the input size, is known as
an auxiliary space. The space complexity considers both the spaces, i.e., auxiliary space, and space
used by the input.

So,

Space complexity = Auxiliary space + Input size.

Types of Algorithms

The following are the types of algorithm:

o Search Algorithm
o Sort Algorithm

Search Algorithm

On each day, we search for something in our day to day life. Similarly, with the case of computer,
huge data is stored in a computer that whenever the user asks for any data then the computer
searches for that data in the memory and provides that data to the user. There are mainly two
techniques available to search the data in an array:

o Linear search
o Binary search

Linear Search

Linear search is a very simple algorithm that starts searching for an element or a value from the
beginning of an array until the required element is not found. It compares the element to be

JJ@MGCP
 6

searched with all the elements in an array, if the match is found, then it returns the index of the
element else it returns -1. This algorithm can be implemented on the unsorted list.

Binary Search

A Binary algorithm is the simplest algorithm that searches the element very quickly. It is used to
search the element from the sorted list. The elements must be stored in sequential order or the
sorted manner to implement the binary algorithm. Binary search cannot be implemented if the
elements are stored in a random manner. It is used to find the middle element of the list.

Sorting Algorithms

Sorting algorithms are used to rearrange the elements in an array or a given data structure either in
an ascending or descending order. The comparison operator decides the new order of the elements.

Why do we need a sorting algorithm?

o An efficient sorting algorithm is required for optimizing the efficiency of other algorithms
like binary search algorithm as a binary search algorithm requires an array to be sorted in
a particular order, mainly in ascending order.
o It produces information in a sorted order, which is a human-readable format.
o Searching a particular element in a sorted list is faster than the unsorted list.

Asymptotic Analysis

Suppose we have an array of 100 elements, and we want to insert a new element at the beginning
of the array. This becomes a very tedious task as we first need to shift the elements towards the
right, and we will add new element at the starting of the array.

Suppose we consider the linked list as a data structure to add the element at the beginning. The
linked list contains two parts, i.e., data and address of the next node. We simply add the address
of the first node in the new node, and head pointer will now point to the newly added node.
Therefore, we conclude that adding the data at the beginning of the linked list is faster than the
arrays. In this way, we can compare the data structures and select the best possible data structure
for performing the operations.

How to find the Time Complexity or running time for performing the operations?

The measuring of the actual running time is not practical at all. The running time to perform any
operation depends on the size of the input. Let's understand this statement through a simple
example.

Suppose we have an array of five elements, and we want to add a new element at the beginning of
the array. To achieve this, we need to shift each element towards right, and suppose each element
JJ@MGCP
 7

takes one unit of time. There are five elements, so five units of time would be taken. Suppose there
are 1000 elements in an array, then it takes 1000 units of time to shift. It concludes that time
complexity depends upon the input size.

Therefore, if the input size is n, then f(n) is a function of n that denotes the time complexity.

How to calculate f(n)?

Calculating the value of f(n) for smaller programs is easy but for bigger programs, it's not that
easy. We can compare the data structures by comparing their f(n) values. We can compare the data
structures by comparing their f(n) values. We will find the growth rate of f(n) because there might
be a possibility that one data structure for a smaller input size is better than the other one but not
for the larger sizes. Now, how to find f(n).

Let's look at a simple example.

f(n) = 5n2 + 6n + 12

where n is the number of instructions executed, and it depends on the size of the input.

When n=1

% of running time due to 5n2 = * 100 = 21.74%

% of running time due to 6n = * 100 = 26.09%

% of running time due to 12 = * 100 = 52.17%

From the above calculation, it is observed that most of the time is taken by 12. But, we have to
find the growth rate of f(n), we cannot say that the maximum amount of time is taken by 12. Let's
assume the different values of n to find the growth rate of f(n).

n 5n2 6n 12

1 21.74% 26.09% 52.17%

10 87.41% 10.49% 2.09%

100 98.79% 1.19% 0.02%

1000 99.88% 0.12% 0.0002%

JJ@MGCP
 8

As we can observe in the above table that with the increase in the value of n, the running time of
5n2 increases while the running time of 6n and 12 also decreases. Therefore, it is observed that for
larger values of n, the squared term consumes almost 99% of the time. As the n 2 term is
contributing most of the time, so we can eliminate the rest two terms.

Therefore,

f(n) = 5n2

Here, we are getting the approximate time complexity whose result is very close to the actual
result. And this approximate measure of time complexity is known as an Asymptotic complexity.
Here, we are not calculating the exact running time, we are eliminating the unnecessary terms, and
we are just considering the term which is taking most of the time.

In mathematical analysis, asymptotic analysis of algorithm is a method of defining the

mathematical boundation of its run-time performance. Using the asymptotic analysis, we can
easily conclude the average-case, best-case and worst-case scenario of an algorithm.

It is used to mathematically calculate the running time of any operation inside an algorithm.

Example: Running time of one operation is x(n) and for another operation, it is calculated as f(n2).
It refers to running time will increase linearly with an increase in 'n' for the first operation, and
running time will increase exponentially for the second operation. Similarly, the running time of
both operations will be the same if n is significantly small.

Usually, the time required by an algorithm comes under three types:

Worst case: It defines the input for which the algorithm takes a huge time.

Average case: It takes average time for the program execution.

Best case: It defines the input for which the algorithm takes the lowest time

Asymptotic Notations
The commonly used asymptotic notations used for calculating the running time complexity of an
algorithm is given below:

o Big oh Notation (?)

o Omega Notation (Ω)
o Theta Notation (θ)

Big oh Notation (O)

JJ@MGCP
 9

o Big O notation is an asymptotic notation that measures the performance of an algorithm by

simply providing the order of growth of the function.
o This notation provides an upper bound on a function which ensures that the function never
grows faster than the upper bound. So, it gives the least upper bound on a function so that
the function never grows faster than this upper bound.

It is the formal way to express the upper boundary of an algorithm running time. It measures the
worst case of time complexity or the algorithm's longest amount of time to complete its operation.
It is represented as shown below:

For example:

If f(n) and g(n) are the two functions defined for positive integers,

then f(n) = O(g(n)) as f(n) is big oh of g(n) or f(n) is on the order of g(n)) if there exists constants
c and no such that:

f(n)≤c.g(n) for all n≥no

This implies that f(n) does not grow faster than g(n), or g(n) is an upper bound on the function f(n).
In this case, we are calculating the growth rate of the function which eventually calculates the
worst time complexity of a function, i.e., how worst an algorithm can perform.

The idea of using big o notation is to give an upper bound of a particular function, and eventually
it leads to give a worst-time complexity. It provides an assurance that a particular function does
not behave suddenly as a quadratic or a cubic fashion, it just behaves in a linear manner in a worst-
case.

Omega Notation (Ω)

o It basically describes the best-case scenario which is opposite to the big o notation.
o It is the formal way to represent the lower bound of an algorithm's running time. It measures
the best amount of time an algorithm can possibly take to complete or the best-case time
complexity.

JJ@MGCP
 10

o It determines what is the fastest time that an algorithm can run.

If we required that an algorithm takes at least certain amount of time without using an upper bound,
we use big- Ω notation i.e. the Greek letter "omega". It is used to bound the growth of running
time for large input size.

If f(n) and g(n) are the two functions defined for positive integers,

then f(n) = Ω (g(n)) as f(n) is Omega of g(n) or f(n) is on the order of g(n)) if there exists constants
c and no such that:

f(n)>=c.g(n) for all n≥no and c>0

Theta Notation (θ)

o The theta notation mainly describes the average case scenarios.

o It represents the realistic time complexity of an algorithm. Every time, an algorithm does
not perform worst or best, in real-world problems, algorithms mainly fluctuate between the
worst-case and best-case, and this gives us the average case of the algorithm.
o Big theta is mainly used when the value of worst-case and the best-case is same.
o It is the formal way to express both the upper bound and lower bound of an algorithm
running time.

Let's understand the big theta notation mathematically:

Let f(n) and g(n) be the functions of n where n is the steps required to execute the program
then:f(n)= θg(n)

The above condition is satisfied only if when c1.g(n)<=f(n)<=c2.g(n)

where the function is bounded by two limits, i.e., upper and lower limit, and f(n) comes in between.
The condition f(n)= θg(n) will be true if and only if c1.g(n) is less than or equal to f(n) and c2.g(n)
is greater than or equal to f(n). The graphical representation of theta notation is given below:

JJ@MGCP
 11

Why we have three different asymptotic analysis?

As we know that big omega is for the best case, big oh is for the worst case while big theta is for
the average case. Now, we will find out the average, worst and the best case of the linear search
algorithm.

Suppose we have an array of n numbers, and we want to find the particular element in an array
using the linear search. In the linear search, every element is compared with the searched element
on each iteration. Suppose, if the match is found in a first iteration only, then the best case would
be Ω(1), if the element matches with the last element, i.e., nth element of the array then the worst
case would be O(n). The average case is the mid of the best and the worst-case, so it
becomes θ(n/1). The constant terms can be ignored in the time complexity so average case
would be θ(n).

So, three different analysis provide the proper bounding between the actual functions. Here,
bounding means that we have upper as well as lower limit which assures that the algorithm will
behave between these limits only, i.e., it will not go beyond these limits.

Common Asymptotic Notations

constant - O(1)

linear - O(n)

logarithmic - O(log n)

n log n - O(n log n)

exponential - O(2(n))

cubic - O(n3)

polynomial - n(1)

quadratic - O(n2)

In theoretical analysis of algorithms, it is common to estimate their complexity in the asymptotic

sense, i.e., to estimate the complexity function for arbitrarily large input. The term "analysis of
algorithms" was coined by Donald Knuth.
Algorithm analysis is an important part of computational complexity theory, which provides
theoretical estimation for the required resources of an algorithm to solve a specific computational
problem. Most algorithms are designed to work with inputs of arbitrary length. Analysis of
algorithms is the determination of the amount of time and space resources required to execute it.

JJ@MGCP
 12

Usually, the efficiency or running time of an algorithm is stated as a function relating the input
length to the number of steps, known as time complexity, or volume of memory, known as space
complexity.
The Need for Analysis
In this chapter, we will discuss the need for analysis of algorithms and how to choose a better
algorithm for a particular problem as one computational problem can be solved by different
algorithms.
By considering an algorithm for a specific problem, we can begin to develop pattern recognition
so that similar types of problems can be solved by the help of this algorithm.
Algorithms are often quite different from one another, though the objective of these algorithms are
the same. For example, we know that a set of numbers can be sorted using different algorithms.
Number of comparisons performed by one algorithm may vary with others for the same input.
Hence, time complexity of those algorithms may differ. At the same time, we need to calculate the
memory space required by each algorithm.
Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm
in terms of the time and size required (the size of memory for storage while implementation).
However, the main concern of analysis of algorithms is the required time or performance.
Generally, we perform the following types of analysis −
 Worst-case − The maximum number of steps taken on any instance of size a.
 Best-case − The minimum number of steps taken on any instance of size a.
 Average case − An average number of steps taken on any instance of size a.
 Amortized − A sequence of operations applied to the input of size a averaged over time.
To solve a problem, we need to consider time as well as space complexity as the program may run
on a system where memory is limited but adequate space is available or may be vice-versa. In this
context, if we compare bubble sort and merge sort. Bubble sort does not require additional
memory, but merge sort requires additional space. Though time complexity of bubble sort is higher
compared to merge sort, we may need to apply bubble sort if the program needs to run in an
environment, where memory is very limited.
Rate of Growth
Rate of growth is defined as the rate at which the running time of the algorithm is increased when
the input size is increased.
The growth rate could be categorized into two types: linear and exponential. If the algorithm is
increased in a linear way with an increasing in input size, it is linear growth rate. And if the
running time of the algorithm is increased exponentially with the increase in input size, it
is exponential growth rate.
In designing of Algorithm, complexity analysis of an algorithm is an essential aspect. Mainly,
algorithmic complexity is concerned about its performance, how fast or slow it works.
The complexity of an algorithm describes the efficiency of the algorithm in terms of the amount
of the memory required to process the data and the processing time.
Complexity of an algorithm is analyzed in two perspectives: Time and Space.

JJ@MGCP
 13

Time Complexity
It’s a function describing the amount of time required to run an algorithm in terms of the size of
the input. "Time" can mean the number of memory accesses performed, the number of
comparisons between integers, the number of times some inner loop is executed, or some other
natural unit related to the amount of real time the algorithm will take.
Space Complexity
It’s a function describing the amount of memory an algorithm takes in terms of the size of input to
the algorithm. We often speak of "extra" memory needed, not counting the memory needed to
store the input itself. Again, we use natural (but fixed-length) units to measure this.
Space complexity is sometimes ignored because the space used is minimal and/or obvious,
however sometimes it becomes as important an issue as time.
Asymptotic Notations
Execution time of an algorithm depends on the instruction set, processor speed, disk I/O speed,
etc. Hence, we estimate the efficiency of an algorithm asymptotically.
Time function of an algorithm is represented by T(n), where n is the input size.
Different types of asymptotic notations are used to represent the complexity of an algorithm.
Following asymptotic notations are used to calculate the running time complexity of an algorithm.

Asymptotic analysis
It is a technique of representing limiting behavior. The methodology has the applications across
science. It can be used to analyze the performance of an algorithm for some large data set.

1. In computer science in the analysis of algorithms, considering the performance of algorithms

when applied to very large input datasets

The simplest example is a function ƒ (n) = n2+3n, the term 3n becomes insignificant compared
to n2 when n is very large. The function "ƒ (n) is said to be asymptotically equivalent to n2 as n
→ ∞", and here is written symbolically as ƒ (n) ~ n2.

Asymptotic notations are used to write fastest and slowest possible running time for an algorithm.
These are also referred to as 'best case' and 'worst case' scenarios respectively.

"In asymptotic notations, we derive the complexity concerning the size of the input. (Example in
terms of n)"

"These notations are important because without expanding the cost of running the algorithm, we
can estimate the complexity of the algorithms."

Why is Asymptotic Notation Important?

1. They give simple characteristics of an algorithm's efficiency.

JJ@MGCP
 14

2. They allow the comparisons of the performances of various algorithms.

Asymptotic Notations:

Asymptotic Notation is a way of comparing function that ignores constant factors and small input
sizes. Three notations are used to calculate the running time complexity of an algorithm:

1. Big-oh notation: Big-oh is the formal method of expressing the upper bound of an algorithm's
running time. It is the measure of the longest amount of time. The function f (n) = O (g (n)) [read
as "f of n is big-oh of g of n"] if and only if exist positive constant c and such that

1. f (n) ⩽ k.g (n)f(n)⩽k.g(n) for n>n0n>n0 in all case

Hence, function g (n) is an upper bound for function f (n), as g (n) grows faster than f (n)

For Example:

1. 1. 3n+2=O(n) as 3n+2≤4n for all n≥2

2. 2. 3n+3=O(n) as 3n+3≤4n for all n≥3

Hence, the complexity of f(n) can be represented as O (g (n))

2. Omega () Notation: The function f (n) = Ω (g (n)) [read as "f of n is omega of g of n"] if and
only if there exists positive constant c and n0 such that

F (n) ≥ k* g (n) for all n, n≥ n0

JJ@MGCP
 15

For Example:

f (n) =8n2+2n-3≥8n2-3
=7n2+(n2-3)≥7n2 (g(n))
Thus, k1=7

Hence, the complexity of f (n) can be represented as Ω (g (n))

3. Theta (θ): The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there
exists positive constant k1, k2 and k0 such that

k1 * g (n) ≤ f(n)≤ k2 g(n)for all n, n≥ n0

For Example:

3n+2= θ (n) as 3n+2≥3n and 3n+2≤ 4n, for n

k1=3,k2=4, and n0=2

Hence, the complexity of f (n) can be represented as θ (g(n)).

The Theta Notation is more precise than both the big-oh and Omega notation. The function f (n) =
θ (g (n)) if g(n) is both an upper and lower bound.

What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the
corresponding function is called a recursive function. Using a recursive algorithm, certain
problems can be solved quite easily. Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. A recursive function
solves a particular problem by calling a copy of itself and solving smaller subproblems of the
original problems. Many more recursive calls can be generated as and when required. It is
essential to know that we should provide a certain case in order to terminate this recursion

JJ@MGCP
 16

process. So we can say that every time the function calls itself with a simpler version of the
original problem.
Need of Recursion
Recursion is an amazing technique with the help of which we can reduce the length of our code
and make it easier to read and write. It has certain advantages over the iteration technique which
will be discussed later. A task that can be defined with its similar subtask, recursion is one of the
best solutions for it. For example; The Factorial of a number.
Properties of Recursion:
 Performing the same operations multiple times with different inputs.
 In every step, we try smaller inputs to make the problem smaller.
 Base condition is needed to stop the recursion otherwise infinite loop will occur.
Algorithm: Steps
The algorithmic steps for implementing recursion in a function are as follows:

Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial.
This is the stopping condition for the recursion, as it prevents the function from infinitely calling
itself.

Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the
problem down into smaller versions of itself, and call the function recursively to solve each
subproblem.

Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches
the base case, and does not enter an infinite loop.

step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original
problem.
A Mathematical Interpretation
Let us consider a problem that a programmer has to determine the sum of first n natural numbers,
there are several ways of doing that but the simplest approach is simply to add the numbers
starting from 1 to n. So the function simply looks like this,
approach(1) – Simply adding one by one
f(n) = 1 + 2 + 3 +……..+ n
but there is another mathematical approach of representing this,
approach(2) – Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
There is a simple difference between the approach (1) and approach(2) and that is
in approach(2) the function “ f( ) ” itself is being called inside the function, so this phenomenon
is named recursion, and the function containing recursion is called recursive function, at the end,

JJ@MGCP
 17

this is a great tool in the hand of the programmers to code some problems in a lot easier and
efficient way.
How are recursive functions stored in memory?
Recursion uses more memory, because the recursive function adds to the stack with each
recursive call, and keeps the values there until the call is finished. The recursive function uses
LIFO (LAST IN FIRST OUT) Structure just like the stack data
structure. [Link]

What is the base condition in recursion?

In the recursive program, the solution to the base case is provided and the solution to the bigger
problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the larger value of a number can
be solved by converting to a smaller one till the base case is reached.
How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller problems, and add one or
more base conditions that stop the recursion. For example, we compute factorial n if we know
the factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Recursion VS Iteration

SR
Recursion Iteration
No.

Terminates when the condition

1) Terminates when the base case becomes true.
becomes false.

2) Used with functions. Used with loops.

Every recursive call needs extra space in the Every iteration does not require any
3)
stack memory. extra space.

4) Smaller code size. Larger code size.

JJ@MGCP
 18

Binary Search Algorithm

Searching is the process of finding some particular element in the list. If the element is present in
the list, then the process is called successful, and the process returns the location of that element.
Otherwise, the search is called unsuccessful.

Linear Search and Binary Search are the two popular searching techniques. Here we will discuss
the Binary Search Algorithm.

Binary search is the search technique that works efficiently on sorted lists. Hence, to search an
element into some list using the binary search technique, we must ensure that the list is sorted.

Binary search follows the divide and conquer approach in which the list is divided into two halves,
and the item is compared with the middle element of the list. If the match is found then, the location
of the middle element is returned. Otherwise, we search into either of the halves depending upon
the result produced through the match.

NOTE: Binary search can be implemented on sorted array elements. If the list elements are not
arranged in a sorted manner, we have first to sort them.

Now, let's see the algorithm of Binary Search.

Algorithm

Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index
of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to sea
rch
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]

JJ@MGCP
 19

Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

Working of Binary search

Now, let's see the working of the Binary Search Algorithm.

To understand the working of the Binary search algorithm, let's take a sorted array. It will be easy
to understand the working of Binary search with an example.

There are two methods to implement the binary search algorithm -

o Iterative method
o Recursive method

The recursive method of binary search follows the divide and conquer approach.

Let the elements of array are -

Let the element to search is, K = 56

We have to use the below formula to calculate the mid of the array -

mid = (beg + end)/2

So, in the given array -

beg = 0

end = 8

mid = (0 + 8)/2 = 4. So, 4 is the mid of the array.

JJ@MGCP
 20

Now, the element to search is found. So algorithm will return the index of the element matched.

Binary Search complexity

Now, let's see the time complexity of Binary search in the best case, average case, and worst case.
We will also see the space complexity of Binary search.

1. Time Complexity

Case Time Complexity

Best Case O(1)

Average Case O(logn)

Worst Case O(logn)

o Best Case Complexity - In Binary search, best case occurs when the element to search is
found in first comparison, i.e., when the first middle element itself is the element to be
searched. The best-case time complexity of Binary search is O(1).
o Average Case Complexity - The average case time complexity of Binary search
is O(logn).

JJ@MGCP
 21

o Worst Case Complexity - In Binary search, the worst case occurs, when we have to keep
reducing the search space till it has only one element. The worst-case time complexity of
Binary search is O(logn).

2. Space Complexity

Space Complexity O(1)

o The space complexity of binary search is O(1).

Tower of Hanoi
1. It is a classic problem where you try to move all the disks from one peg to another peg using
only three pegs.

2. Initially, all of the disks are stacked on top of each other with larger disks under the smaller
disks.

3. You may move the disks to any of three pegs as you attempt to relocate all of the disks, but you
cannot place the larger disks over smaller disks and only one disk can be transferred at a time.

This problem can be easily solved by Divide & Conquer algorithm

In the below 7 step all the disks from peg A will be transferred to C given Condition:

1. Only one disk will be shifted at a time.

2. Smaller disk can be placed on larger disk.

Let T (n) be the total time taken to move n disks from peg A to peg C

1. Moving n-1 disks from the first peg to the second peg. This can be done in T (n-1)
steps.
2. Moving larger disks from the first peg to the third peg will require first one step.
3. Recursively moving n-1 disks from the second peg to the third peg will require
again T (n-1) step.

So, total time taken T (n) = T (n-1)+1+ T(n-1)

JJ@MGCP
 22

JJ@MGCP