MODULE I

1. INTRODUCTION

2. PERFORMANCE ANALYSIS

2.1 Space Complexity

2.2 Time Complexity

3. ASYMPTOTIC NOTATIONS (O, Ω, and θ)

3.1 The notation O (big ‘oh’)

3.2 The notation Ω (big ‘omega’)

3.3 The notation θ(Theta)

4. ANALYSIS AND COMPLEXITY OF ALGORITHMS

4.1 Best, Worst and Average cases

5. RECURSION

5.1 Analysis of Recursion

5.1.1 Time Complexity

5.1.2 Space Complexity

5.2 Removal of recursion through iteration

5.3 Recursive and no-recursive algorithms for Binary Search

6. Big O Notation

PraveenKumar P K, UIT KOllam

1. INTRODUCTION
Q) What is an Algorithm?
 An Algorithm is a set of rules for carrying out calculation either by hand or on a
machine.
 An Algorithm is a well defined computational procedure that takes input and produces
output.
 An Algorithm is a finite sequence of instructions or steps (i.e. inputs) to achieve some
particular output.
 An Algorithm is a well-defined procedure that allows a computer to solve a problem.
Another way to describe an algorithm is a sequence of unambiguous instructions.

Algorithms are used to convert our problem

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

Q) What are the properties of a good algorithm?

 Finiteness: The algorithm must always terminate after a finite number of steps.
 Definiteness: Each step must be precisely defined; the actions to be carried out must
be rigorously and unambiguously specified for each case.
 Input: An algorithm has zero or more inputs, taken from a specified set of objects.
 Output: An algorithm has one or more outputs, which have a specified relation to the
inputs.
 Effectiveness: All operations to be performed must be sufficiently basic that they
can be done exactly and in finite length.
Problems vs Algorithms vs Programs
For each problem or class of problems, there may be many different algorithms. For each
algorithm, there may be many different implementations (programs).

PraveenKumar P K, UIT KOllam

2. PERFORMANCE ANALYSIS
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 analyse them and pick
the one which is best suitable for our requirements. Formal definition is as follows
Performance of an algorithm is a process of making evaluative judgment about algorithms.
That means when we have multiple algorithms to solve a problem, we need to select a
suitable algorithm to solve that problem.
We compare all algorithms with each other which are solving same problem, to select best
algorithm. To compare algorithms, we use a set of parameters or set of elements like
memory required by that algorithm, 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 analyse an algorithm, we consider only the space and time required by that
particular algorithm and we ignore all 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 required by that
algorithm and time required by that algorithm.
Performance analysis of an algorithm is performed by using the following measures...
1. Space required to complete the task of that algorithm (Space Complexity). It
includes program space and data space
2. Time required to complete the task of that algorithm (Time Complexity)
a. 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. Memory required to store program instructions
2. Memory required to store constant values
3. Memory required to store variable values
4. And for few other things
Space complexity of an algorithm can be defined as
Total amount of computer memory required by an algorithm to complete its execution is
called as space complexity of that algorithm

PraveenKumar P K, UIT KOllam

Generally, when a program is under execution it uses the computer memory for THREE
reasons. They are as follows...
1. Instruction Space: It is the amount of memory used to store compiled version of
instructions.
2. Environmental Stack: It is the amount of memory used to store information of
partially executed functions at the time of function call.
3. Data Space: It is the amount of memory used to store all the variables and
constants.
To calculate the space complexity, we must know the memory required to store different
datatype values (according to the compiler). For example, the C Programming Language
compiler requires the following...
1. 2 bytes to store Integer value,
2. 4 bytes to store Floating Point value,
3. 1 byte to store Character value,
4. 6 (OR) 8 bytes to store double value
Example 1
Consider the following piece of code
int square(int a)
{
return a*a;
}
In above piece of code, it requires
2 bytes of memory to store variable 'a' and
Another 2 bytes of memory is used for return value.
That means, totally it requires 4 bytes of memory to complete its execution. And this 4
bytes of memory is fixed for any input value of 'a'. This space complexity is said to be
Constant Space Complexity.
Example 2
Consider the following piece of code...
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
In above piece of code it requires
'n*2' bytes of memory to store array variable 'a[]'
2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)
2 bytes of memory for return value.

PraveenKumar P K, UIT KOllam

That means, totally it requires '2n+8' bytes of memory to complete its execution. Here, the
amount of memory depends on the input value of 'n'. This space complexity is said to be
Linear Space Complexity.
b. 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.
Time complexity of an algorithm can be defined as
The time complexity of an algorithm is the total amount of time required by an algorithm to
complete its execution.

Generally, 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 time it takes to perform Arithmetic operations, logical operations, return value
and assignment operations etc.,
5. Input data
Example 1
Consider the following piece of code...
int sum(int a, int b)
{
return a+b;
}
In above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time to return
the value. That means, totally it takes 2 units of time to complete its execution. And it does
not change based on the input values of a and b. That means for all input values, it requires
same amount of time i.e. 2 units.
If any program requires fixed amount of time for all input values then its time complexity is
said to be Constant Time Complexity.
Example 2
Consider the following piece of code...
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
For the above code, time complexity can be calculated as follows

PraveenKumar P K, UIT KOllam

In above calculation
Cost is the amount of computer time required for a single operation in each line.
Repeatation is the amount of computer time required by each operation for all its
repeatations.
Total is the amount of computer time required by each operation to execute.
So above code requires '4n+4' Units of computer time to complete the task. Here the
exact time is not fixed. And it changes based on the n value. If we increase the n value then
the time required also increases linearly.
Totally it takes '4n+4' units of time to complete its execution and it is Linear 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

3. ASYMPTOTIC NOTATIONS (O, Ω, and θ)

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

There are three basic asymptotic notations which are used to express the running time of
an algorithm in terms of function, whose domain is the set of natural numbers N={1,2,3,…..}.
These are:
 O (Big - Oh): This notation is used to express Upper bound (maximum steps) required
to solve a problem
 Ω (Big - Omega): This notation is used to express Lower bound i.e. minimum (at least)
steps required to solve a problem
 Θ (Big - Theta): This notation is used to express both Upper & Lower bound, also
called tight bound
Asymptotic notation gives the rate of growth, i.e. performance, of the run time for
“sufficiently large input sizes” and is not a measure of the particular run time for a specific
input size (which should be done empirically). O-notation is used to express the Upper bound
(worst case); Ω-notation is used to express the Lower bound (Best case) and Θ- Notations
is used to express both upper and lower bound (i.e. Average case) on a function. We
generally want to find either or both an asymptotic lower bound and upper bound for the
growth of our function. The lower bound represents the best case growth of the algorithm
while the upper bound represents the worst case growth of the algorithm.

PraveenKumar P K, UIT KOllam

3.1 The notation O (big ‘oh’)
Big ‘Oh’ Notation is used to express an asymptotic upper bound (maximum steps) for a given
function f(n). Let f(n) and g(n) are two positive functions , each from the set of natural
numbers (domain) to the positive real numbers. We say that the function f(n) = O(g(n))
(read as “f of n is big ‘Oh’ of g of n”), if there exist two positive constants C and n 0 such
that :
f(n) ≤ C.g(n), for all n ≥ n0
The intuition behind O- notation is shown below

For all values of n to the right of n0, the value of f(n) is always lies on or below C.g(n)
To understand O-Notation let us consider the following examples
Q) For the function defined by f(n) = 2n2+3n+1 : show that
i. f(n) = O(n2)
ii. f(n) = O(n3)
Solution
(i) To show that f(n) = O(n2) ; we have to show that
f(n) ≤ C.g(n), for all n ≥ n0
ie, 2n2+3n+1 ≤ C. n2
clearly this equation is satisfied for C = 6 and for all n >= 1
2n2+3n+1 ≤ 6.n2 for all n >= 1
since we have found the required constant C = 6 and n 0 = 1 . Hence f(n) = O(n2)
The value of C and n0 is not unique. For example, to satisfy the above equation , we
can also take C=3 and n>=3 . So depending on the value of C, the value of n 0 is also
changes. Thus any value of C and n0 which satisfy the given inequality is a valid
solution.
(ii) To show that f(n) = O(n3); we have to show that
f(n) ≤ C.g(n), for all n ≥ n0
ie, 2n2+3n+1 ≤ C. n3 Let C = 3
Value of n 2n2+3n+1 3 n3
1 6 3

PraveenKumar P K, UIT KOllam

 2 15 24
3 27 81
…… …… ……
clearly this equation is satisfied for C = 3 and for all n >= 2
2n2+3n+1 ≤ 3.n3 for all n >= 2
since we have found the required constant C = 3 and n 0 = 2. Hence f(n) = O(n3)
3.2 The notation Ω (big ‘omega’)
O- Notation provides an asymptotic upper bound for a function; Ω-Notation, provides an
asymptotic lower-bound for a given function. We say that the function f(n) = Ω(g(n)) (read
as “f of n is big ‘Omega’ of g of n”), if and only if there exist two positive constants C and n 0
such that
f(n) ≥ C.g(n), for all n ≥ n0
The intuition behind Ω- notation is shown below

Note that for all values of f(n) always lies on or above g(n).
To understand Ω-Notation let us consider the following examples
Q) For the function defined by f(n) = 2n3+3n2+1 and g(n) = f(n) = 2n2+3n show that
i) f(n) = Ω(g(n))
ii) g(n) ≠ Ω(f(n))
Solution
i) To show that f(n) = Ω(g(n)) we have to show that f(n) ≥ C.g(n), for all n ≥ n 0
2n3+3n2+1 ≥ C(2n2+3n)
This equation satisfied for C=1 and n0 = 1
Hence f(n) = Ω(g(n))
3.3 The notation θ(Theta)
Θ-Notation provides simultaneous both asymptotic lower bound and asymptotic upper bound
for a given function. Let f(n) and g(n) are two positive functions , each from the set of
natural numbers (domain) to the positive real numbers. In some cases, we have
f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = θ(g(n)).

PraveenKumar P K, UIT KOllam

We say that the function f(n) = θ(g(n)) (read as “f of n is ‘Theta’ of g of n”), if and only if
there exist three positive constants C1, C2 and n0 such that
C1.g(n) ≤ f(n) ≤ C2.g(n) for all n ≥ n0
Note that this inequality represents two conditions to be satisfied simultaneously viz
C1.g(n) ≤ f(n) and f(n) ≤ C2.g(n)
Clearly this implies
If f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = θ(g(n)).
The following figure shows the intuition behind the Θ-Notation.

Note that for all values of n to the right of the n0 the value of f(n) lies at or above C 1.g(n)
and at or below C2.g(n).
To understand Ω-Notation let us consider the following example
Q) For the function defined by f(n) = 2n3+3n2+1 and g(n) = 2n3+1 show that f(n) = θ(g(n)).
Solution
To show that f(n) = θ(g(n)) we have to show that
C1.g(n) ≤ f(n) ≤ C2.g(n) for all n ≥ n0
C1(2n3+1) ≤ 2n3+3n2+1 ≤ C2(2n3+1) for all n ≥ n0 …………………….(1)
To satisfy this inequality simultaneously, we have to find the value of C 1, C2 and n0
using the following inequality
C1(2n3+1) ≤ 2n3+3n2+1 …………………..(2) and
2n3+3n2+1 ≤ C2(2n3+1) ………………….(3)
Inequality (2) is satisfied for C1 = 1 and n ≥ 1 (ie, n0 = 1)
Inequality (3) is satisfied for C2 = 2 and n ≥ 1 (ie, n0 = 1)
Hence inequality (1) simultaneously satisfied for C 1 = 1, C2 = 2 and n ≥ 1
Hence f(n) = θ(g(n)).

PraveenKumar P K, UIT KOllam

4. ANALYSIS AND COMPLEXITY OF ALGORITHMS

Analysis of algorithm is a field in computer science whose overall goal is an understanding

of the complexity of algorithms in terms of Time Complexity also known as Execution Time
& Storage (or Space) requirement taken by that algorithm.

Suppose M is an algorithm, and suppose n is the size of the input data. The time and space
used by the algorithm M are the two main measures for the efficiency of M.
 The time is measured by counting the number of key operations, for example, in case
of sorting and searching algorithms, the number of comparisons is the number of key
operations. That is because key operations are so defined that the time for the other
operations is much less than or at most proportional to the time for the key
operations.
 The space is measured by counting the maximum of memory needed by the algorithm.
The complexity of an algorithm M is the function f(n), which give the running time and/or
storage space requirement of the algorithm M in terms of the size n of the input data.
Frequently, the storage space required by an algorithm is simply a multiple of the data size
n. In general the term “complexity” given anywhere simply refers to the running time of the
algorithm. There are 3 cases, in general, to find the complexity function f(n)
1. Best case The minimum value of f(n) for any possible input.
2. Worst case The maximum value of f(n)for any possible input.
3. Average case The value of f(n) which is in between maximum and minimum for any
possible input. Generally the Average case implies the expected value of f(n)
4.1 Best, Worst and Average cases
To better understand all of the 3 cases, consider an example of English dictionary, used to
search a meaning of a particular word.
Best Case: Suppose we open a dictionary and luckily we get the meaning of a word which we
are looking for. This requires only one step (minimum possible) to get the meaning of a word.
Worst case: Suppose you are searching a meaning of a word and that word is either not in a
dictionary or that word takes maximum possible steps (i.e. now no left hand side or right
hand side page is possible to see).
Average Case: If you are searching a word for which neither a Minimum (best case) nor a
maximum (worst case) steps are required is called average case. In this case, we definitely
get the meaning of that word.
Example 1: Linear Search
To understand the Best, Worst and Average cases of an algorithm, consider a linear array
A[1….n], where the array A contains n-elements. Suppose you want either to find the
location LOC of a given element (say ‘x’) in the given array A or to send some message, such

PraveenKumar P K, UIT KOllam

as LOC=0, to indicate that ‘x’ does not appear in A. Here the linear search algorithm solves
this problem by comparing given, one-by-one, with each element in A. That is, we compare ‘x’
with A[1], then A[2], and so on, until we find LOC such that x = A[LOC].

Analysis of linear search algorithm

The complexity of the search algorithm is given by the name C of comparisons between x
and array elements A[K].
Best case: Clearly the best case occurs when ‘x’ is the first element in the array A. That is
x = A[LOC]. In this case C(n) = 1 = O(1).
Worst case: Clearly the worst case occurs when ‘x’ is the last element in the array A or ‘x’
is not present in given array A (to ensure this we have to search entire array A till last
element). In this case, we have C(n) = n = O(n).
Average case: Here we assume that searched element ‘x’ appear array A, and it is equally
likely to occur at any position in the array. Here the number of comparisons can be any of
numbers 1, 2, 3… n, and each number occurs with the probability p = 1/n then
C(n) = 1(1/n) + 2(2/n) + …… + n(1/n)
=(1 + 2 + …... + n).1/n
=(n(n+1)/2).1/n
=(n+1)/2
It means the average number of comparisons needed to find the location of x is
approximately equal to half the number of elements in array A. From above discussion, it
may be noted that the complexity of an algorithm in the average case is much more

PraveenKumar P K, UIT KOllam

complicated to analyze than that of worst case. Unless otherwise stated or implied, we
always find and write the complexity of an algorithm in the worst case.
Example 2: Binary search
A Binary search is a well known searching algorithm which follows the same concept of
English dictionary. To understand a Binary search algorithm consider a sorted linear array
A[1…n], Suppose you want either to find(or search) the location LOC of a given element (say
‘x’) in the given array A (successful search) or to send some message, such as LOC=0, to
indicate that ‘x’ does not appear in A(Unsuccessful search). A Binary search algorithm is an
efficient technique for finding a position of specified value (say ‘x’) within a sorted array A.
The Binary search algorithm proceeds as follow
1) Begin with the interval covering the whole array; binary search repeatedly divides
the search interval (i.e. Sorted array A) in half.
2) At each step, the algorithm compares the given input key (or search) value ‘x’ with
the key value of the middle element of the array A.
3) If it match, then a searching element ‘x’ has been found so its index, or position, is
returned. Otherwise, if the value of the search element ‘x’ is less than the item in
the middle of the interval; then the algorithm repeats its action on the sub-array to
the left of the middle element or, if the search element ‘x’ is greater than the
middle element‟s key, then on the sub-array to the right.
4) We repeatedly check until the searched element is found (i.e. x = A[LOC]) or the
interval is empty, which indicates ‘x’ is “not found”.
Analysis of Binary search algorithm
Best Case: Clearly the best case occurs when you divide the array 1st time and you get the
searched element ‘x’. This requires only one step (minimum possible step). In this case, the
number of comparison C(n) = 1 = O(1).
Worst case: Suppose you are searching a given key ‘x’ and that ‘x’ is either not in a given
array A[1…n] or to search that element ‘x’ takes maximum possible steps (i.e. now no left
hand side or right hand side elements in array A is possible to see). Clearly the worst case
occurs, when ‘x’ is searched at last.
Let us assume for the moment that the size of the array is a power of 2, say 2 k. Each time
when we examine the middle element, we cut the size of the sub-array is half.
So before the 1st iteration size of the array is: 2k
After the 1st iteration size of the sub-array of our interest is: 2k-1
After the 2nd iteration size of the sub-array of our interest is: 2k-2
………………………………………………
After the kth iteration size of the sub-array of our interest is: 2k-k = 1
So we stop now for the next iteration. Thus we have at most
(k+1) = (log n +1) iterations.

PraveenKumar P K, UIT KOllam

Since with each iteration, we perform a constant amount of work: Computing a mid point and
few comparisons. So overall, for an array of size n, we perform C.(log n +1) = O(log n)
comparisons
Average Case: If you are searching given key ‘x’ for which neither a Minimum (best case)
nor a maximum (worst case) steps are required is called average case. In this case, we
definitely get the given key ‘x’ in the array A. In this case also C(n) = O(logn)
The following table summarizes the time complexity of Linear Search and Binary Search in
various cases
Algorithm Best Case Average Case Worst case
Linear Search O(1) O(n) O(n)
Binary Search O(1) O(logn) O(logn)
5. RECURSION
Recursion is a very powerful technique to write a complicated algorithm in a easy way. For
solving any big problem we divide it in smaller ones. Then we can group them into problem
which have near about same logic.
Some computer programming languages allow a module or function to call itself. This
technique is known as recursion. In recursion, a function A either calls itself directly or
calls a function B that in turn calls the original function A. The function A is called recursive
function.
Properties
A recursive function can go infinite like a loop. To avoid infinite running of recursive
function, there are two properties that a recursive function must have −
 Base criteria − There must be at least one base criteria or condition, such that, when
this condition is met the function stops calling itself recursively.
 Progressive approach − The recursive calls should progress in such a way that each
time a recursive call is made it comes closer to the base criteria
Implementation
Many programming languages implement recursion by means of stacks. Generally, whenever a
function (caller) calls another function (callee) or itself as callee, the caller function
transfers execution control to the callee. This transfer process may also involve some data
to be passed from the caller to the callee.
This implies, the caller function has to suspend its execution temporarily and resume later
when the execution control returns from the callee function. Here, the caller function
needs to start exactly from the point of execution where it puts itself on hold. It also
needs the exact same data values it was working on. For this purpose, an activation record
(or stack frame) is created for the caller function. This activation record keeps the
information about local variables, formal parameters, return address and all information
passed to the caller function.

PraveenKumar P K, UIT KOllam

5.1 Analysis of Recursion
One may argue why to use recursion, as the same task can be done with iteration. The first
reason is, recursion makes a program more readable and because of latest enhanced CPU
systems, recursion is more efficient than iterations.
5.1.1 Time Complexity
In case of iterations, we take number of iterations to count the time complexity. Likewise,
in case of recursion, assuming everything is constant, we try to figure out the number of
times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number
of times a recursive call is made makes the recursive function Ο(n).
5.1.2 Space Complexity
Space complexity is counted as what amount of extra space is required for a module to
execute. In case of iterations, the compiler hardly requires any extra space. The compiler
keeps updating the values of variables used in the iterations. But in case of recursion, the
system needs to store activation record each time a recursive call is made. Hence, it is
considered that space complexity of recursive function may go higher than that of a
function with iteration.
5.2 Removal of recursion through iteration
We can use iteration to replace recursion. Let us take a simple example of factorial throudh
recursion and as well as recursion.
factorial(no)
{
fact = 1;
if(no > 1)
fact = no * factorial( no - 1)
return fact
}
Suppose we want to get the factorial of 4 then the whole process will be as

PraveenKumar P K, UIT KOllam

 factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1
Now the value will be return back to the previous called function as
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
Here we can take the whole process take 7 steps. Getting values in stack, calculation and
returning values to stack is also time consuming and takes extra spaces. Same thing can be
replaced with iteration as
factorial(no)
{
fact = 1
for(i = 0; i > 1; i--)
fact = fact * i
return fact
}
Here we can see recursion is replaced very easily with iteration. Here iteration takes less
steps, space, and time.
5.3 Recursive and no-recursive algorithms for Binary Search
Let aᵢ, 1 ≤ i ≤ n, be a list of elements that are stored in non-decreasing order. Consider the
problem of determining whether a given element x is present in the list. If x is present, we
are determine a value j such that aj = x. If x is not in the list, then j is set to be zero. Let
P= (n, ai, …., al, x) denote an arbitrary instance of this search problem (n is the number of
elements in the list, ai, …., aj is the list of elements, and x is the element for search for).
Divide-and-conquer can be used to solve this problem. Let Small(P) be true if n = 1. In this
case S(P) will take the value i if x = ai ; Otherwise it will take the value 0. Then g(1) = Θ(1).
If P has more than one element, it can be divided into a new sub-problem as follows. Pick an
index q in the range [i, l] and compare x with aq. There are three possibilities:
1. x = aq : In this case the problem P is immediately solved.
2. x < aq : In this case x has to be searched for only the sub-list a i,ai-1,….,aq-1,x).
3. x > aq : In this case sublist to be searched is aq+1,…..,aj . P produces to ( l -
q,aq+1,….,al,x).
In this example, any given problem P gets divided into one new sub-problem. This division
takes only Θ(1) time. After a comparison with aq , the instance remaining to the solved (if
any) can be solved by using this divide-and-conquer scheme again. If q is always chosen such
that aq is the middle element (i.e. q = (n+1)/2), then the resulting search algorithm known as
Binary Search. Note that the answer of the new sub-problem is also the answer of original
problem P; There is no need for any combining.
Algorithm 1 describes this Binary Search method, where BinSearch has four input a[ ], i, l,
and x. It is initially involved as BinSearch( a, 1, n, x).

PraveenKumar P K, UIT KOllam

Algorithm 1: Recursive Binary Search
BinSearch(a[], i, l, x)
// Give an array a[i:l] of elements in non-decreasing order,
// 1≤i≤l, determine whether x is present, and if so, return j
// such that x = a[j]; else return 0.
{
if(l=i) then // if Small(P)
{
if(x=a[i]) then return i;
else return 0;
}
else
{
//Reduce P into smaller Sub-Problem.
mid = (i+l)/2;
if(x=a[mid]) then return mid;
else if(x < a[mid]) then
return BinSearch(a, i, mid-1, x);
else return BinSearch(a,mid+1,l,x);
}
}
A non-recursive version of BinSearch is given in Algorithm 2. BinSearch has three inputs a,
n, & x. The while loop continues processing as long as there more elements left to check. At
the conclusion of procedure 0 is return if x is not present, or j is returned, such that a[j]=x.
We observe that low & high are integer variable such that each time through the loop either
x is found or low is increased by at least one or high is decreased by at least one. Thus we
have to sequences of integers approaching each other and eventually low become greater
than high and cause termination in a finite number of steps if x is not present.
Algorithm 2: Non-Recursive Binary Search
BinSearch(a, n, x)
// Give an array a[1:n] of elements in non-decreasing order, n≥0,
// determine whether x is present, and if so, return j such that x=a[j]; else return 0.
{
low:=1; high:=n;
while(low ≤ high)
{
mid:=(low+high)/2;
if(x < a[mid]) then high = mid – 1;
else if (x > a[mid]) then low = mid + 1;
else return mid;
}
return 0;
}

PraveenKumar P K, UIT KOllam

Example: Let us consider 14 entries: -15,-6,0,7,9,23,54,82,101,112,125,131,142,151
Place them in a[1:14] and simulate the steps that BinSearch goes through as it searches for
different values of x. Only the variables low, high and mid need to be traced as we simulate
the algorithm. We try the following values for x: 151,-14,9 for two successful searches and
one unsuccessful search. The traces of these three inputs shows below:

X = -14 low high mid X = 151 low high mid X = 9 low high mid
1 14 7 1 14 7 1 14 7
1 6 3 8 14 11 1 6 3
4 6 5
1 2 1 12 14 13
Found
2 2 2 14 14 14
2 1 Not Found Found

To test all successful searches, x must take on the n values for a. To test all unsuccessful
searches, x must take on the n+1 values for a. Thus complexity of BinSearch is 2n+1 for
each n.
Now Let analyze the execution profile of BinSearch. The two relevant characteristics of
this profile are the frequency count and space required of the n elements of the array plus
the variables low, high, mid and x, or n+4 locations. As for the time, there are three
possibilities to consider: the best, average and worst cases.
Suppose we begin determining the time for BinSearch on the previous data set. We observe
that the only operations in the algorithm are comparisons and some arithmetic and data
movements. We concentrate on comparisons between x and the elements in a[ ], recognizing
that the frequency count of all other operations is of the same order as that for these
comparisons. We assume that only one comparisons needed to determine which of the three
possibilities of the if statement holds. The number of element comparison needed to find
each of the 14 elements is

a: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]
Elements: -15 -6 0 7 9 23 54 82 101 112 125 131 142 151
Comparisons: 3 4 2 4 3 4 1 4 3 4 2 4 3 4
No elements require more than 4 comparisons to be found. The average is obtained by
summing the comparisons need to find all 14 items and dividing by 14. These yields 45/14, or
approximately 3.21, comparisons per successful search on the average. There are 15
possible ways that an unsuccessful search may terminate depending on the value of x. If x <
a[1], the algorithm requires 3 element comparison to determine that x is not present. For all
the remaining possibilities, BinSearch require 4 element comparisons. Thus the average
number of element comparisons for an unsuccessful search is (3 + 14* 4) / 15 = 59 / 15
=3.93.
The analysis just done applies to any stored sequence containing 14 elements. But the result
we would prefer is a formula for n elements. A good way to derive such a formula plus a
better way to understand the algorithm is to consider the sequence of values for mid that
are produced by BinSearch for all possible values for x. These values are nicely described

PraveenKumar P K, UIT KOllam

using a binary decision tree in which the value in each node is the value of mid. For example ,
if n=14, then below figure contain a binary decision tree that traces the way in which these
values are produced by BinSearch.

The first comparison is x with a[7]. If xa[7], then the next comparison is a[3]; similarly, if x
> a[7], then the next comparisons is with a [11]. Each path through the tree represents a
sequence of comparison in the binary search method. If x is present, then the algorithm will
end at one of the circular nodes that lists the index into the array where x was found. If x
is not present, the algorithm will terminate at one of the square nodes. Circular nodes are
called internal node & square nodes are called external nodes.
Complexity

Successful Search Unsuccessful Search

Best Case Average Worst Best Case Average Worst
O(1) O(log n) O(log n) O(log n) O(log n) O(log n)

6. Big O Notation
Big O Notation (with a capital letter O, not a zero), also called Landau's symbol, is a
symbolism used in complexity theory, computer science, and mathematics to describe the
asymptotic behavior of functions. Basically, it tells you how fast a function grows or
declines.
Landau's symbol comes from the name of the German number theoretician Edmund Landau
who invented the notation. The letter O is used because the rate of growth of a function is
also called its order.
Here is a list of classes of functions that are commonly encountered when analyzing
algorithms. The slower growing functions are listed first. c is some arbitrary constant.
No Notation Name No Notation Name
1. O(1) Constant 6. O(n )
c
Polynomial
2. O(log(n)) Logarithmic 7. O(c )
n
Exponential

PraveenKumar P K, UIT KOllam

3. O((log(n))c) Polylogarithmic
4. O(n) Linear
5. O(n2) Quadratic
Questions

1. What is an Algorithm?

2. Explain the Properties of a good Algorithm

3. What is mean by asymptotic notation? Explain

4. What is a Stable Algorithm?

5. Differentiate between Algorithm and pseudo code

6. What is order of growth? Describe the best average and worst case efficiency

7. Explain the time complexity of an algorithm

8. Define search and sort

9. Explain Binary search

10. Explain Recursion

11. List different stable sort algorithms

Comparison of different sorting algorithms

Name Best Average Worst Stable

Quicksort n log n n log n n2 Depends

Merge sort n log n n log n n log n Yes

Heapsort n log n n log n n log n No

Introsort n log n n log n n log n No

Insertion sort n n2 n2 Yes

Selection sort n2 n2 n2 No

Timsort n n log n n log n Yes

n (log n)2

Shell sort n or n (log n)2 No

n3/2

Bubble sort n n2 n2 Yes

PraveenKumar P K, UIT KOllam