UNIT I INTRODUCTION

Basic Terminologies: Elementary Data Organizations, Data Structure and its Operations;
Algorithm, Asymptotic Notations, Time, Space Complexity, Recursion. Searching: Linear
Search and Binary Search Techniques, and their complexity.

Basic Terminology: Elementary Data Organization:

Data: Data are simply values or sets of values.

Data items: Data items refers to a single unit of values.

Data items that are divided into sub-items are called Group items. Ex: An Employee
Namemay be divided into three subitems- first name, middle name, and last name.

Data items that are not able to divide into sub-items are called Elementary items.

Ex: SSN

Entity: An entity is something that has certain attributes or properties which may be assigned
values. The values may be either numeric or non-numeric.
Ex: Attributes- Names, Age, Sex, SSN
Values- Rohland Gail, 34, F, 134-34-5533

Entities with similar attributes form an entity set. Each attribute of an entity set has a range of
values, the set of all possible values that could be assigned to the particular attribute.
The term “information” is sometimes used for data with given attributes, of, in other
wordsmeaningful or processed data.

Field is a single elementary unit of information representing an attribute of an entity.

Record is the collection of field values of a given entity.

File is the collection of records of the entities in a given entity set.

Each record in a file may contain many field items but the value in a certain field may uniquely
determine the record in the file. Such a field K is called a primary key and the values k1,

1
k2,….. in such a field are called keys or key values.

Records may also be classified according to length.

A file can have fixed-length records or variable-length records.

• In fixed-length records, all the records contain the same data items with the same
amountof space assigned to each data item.
• In variable-length records file records may contain different lengths.

Example: Student records have variable lengths, since different students take different
numbers of courses. Variable-length records have a minimum and a maximum length.

The above organization of data into fields, records and files may not be complex enough to
maintain and efficiently process certain collections of data. For this reason, data are also
organized into more complex types of structures.

The study of complex data structures includes the following three steps:
1. Logical or mathematical description of the structure

2. Implementation of the structure on a computer

3. Quantitative analysis of the structure, which includes determining the amount of

memory needed to store the structure and the time required to process the structure.

DATA STRUCTURES

Data may be organized in many different ways. The logical or mathematical model of a
particular organization of data is called a data structure.

The choice of a particular data model depends on the two considerations

1. It must be rich enough in structure to mirror the actual relationships of the data in
thereal world.
2. The structure should be simple enough that one can effectively process the

2
 datawhenever necessary.

CLASSIFICATION OF DATA STRUCTURES

Data structures are generally classified into

• Primitive data Structures
• Non-primitive data Structures

1. Primitive data Structures: Primitive data structures are the fundamental data types
which are supported by a programming language. Basic data types such as integer, real,
character and Boolean are known as Primitive data Structures. These data types consists of
characters that cannot be divided and hence they also called simple data types.

2. Non- Primitive data Structures: Non-primitive data structures are those data structures
which are created using primitive data structures. Examples of non-primitive data
structures is the processing of complex numbers, linked lists, stacks, trees, and graphs.

Based on the structure and arrangement of data, non-primitive data structures is further
classified into

1. Linear Data Structure

2. Non-linear Data Structure

1. Linear Data Structure:

A data structure is said to be linear if its elements form a sequence or a linear list. There
arebasically two ways of representing such linear structure in memory.

1. One way is to have the linear relationships between the elements represented by

3
 means of sequential memory location. These linear structures are called arrays.
2. The other way is to have the linear relationship between the elements represented
by means of pointers or links. These linear structures are called linked lists.

The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists

2. Non-linear Data Structure:

A data structure is said to be non-linear if the data are not arranged in sequence or a linear. The
insertion and deletion of data is not possible in linear fashion. This structure is mainly used to
represent data containing a hierarchical relationship between elements. Trees and graphs are
the examples of non-linear data structure.

Arrays:

The simplest type of data structure is a linear (or one dimensional) array. A list of a finite
number n of similar data referenced respectively by a set of n consecutive numbers,
usually 1, 2, 3 . . . . . . . n. if A is chosen the name for the array, then the elements of A are
denoted by subscript notation a1, a2, a3….. an
or
by the parenthesis notation……..A (1), A (2), A (3) A (n)
or
by the bracket notation…………..A [1], A [2], A [3] A [n]

Example 1: A linear array STUDENT consisting of the names of six students is pictured
in below figure. Here STUDENT [1] denotes John Brown, STUDENT [2] denotes

4
 Sandra Gold, and so on.

Linear arrays are called one-dimensional arrays because each element in such an array is
referenced by one subscript. A two-dimensional array is a collection of similar data elements
where each element is referenced by two subscripts.

Example 2: A chain of 28 stores, each store having 4 departments, may list its weekly sales
as in below fig. Such data can be stored in the computer using a two-dimensional array in
which the first subscript denotes the store and the second subscript the department. If SALES
is the name given to the array, then
SALES [1, 1] = 2872, SALES [1, 2] - 805, SALES [1, 3] = 3211,…., SALES [28, 4] = 982

Trees

Data frequently contain a hierarchical relationship between various elements. The data
structure which reflects this relationship is called a rooted tree graph or a tree.
Some of the basic properties of tree are explained by means of examples

Example 1: Record Structure

Although a file may be maintained by means of one or more arrays a record, where one
indicates both the group items and the elementary items, can best be described by means of a
tree structure.
For example, an employee personnel record may contain the following data items:

Social Security Number, Name, Address, Age, Salary, Dependents

5
However, Name may be a group item with the sub-items Last, First and MI (middle initial).
Also Address may be a group item with the sub-items Street address and Area address, where
Area itself may be a group item having sub-items City, State and ZIP code number.
This hierarchical structure is pictured below:

Another way of picturing such a tree structure is in terms of levels, as shown below

Some of the data structures are briefly described below.

1. Stack: A stack, also called a fast-in first-out (LIFO) system, is a linear list in which insertions
and deletions can take place only at one end, called the top. This structure is similar in its
operation to a stack of dishes on a spring system as shown in fig.
Note that new 4 dishes are inserted only at the top of the stack and dishes can be deleted only
from the top of the Stack.
6
2. Queue: A queue, also called a first-in first-out (FIFO) system, is a linear list in which
deletions can take place only at one end of the list, the "from'' of the list, and insertions can take
place only at the other end of the list, the “rear” of the list.
This structure operates in much the same way as a line of people waiting at a bus stop, as
pictured in Fig. the first person in line is the first person to board the bus. Another analogy is
with automobiles waiting to pass through an intersection the first car in line is the first car
through.

3. Graph: Data sometimes contain a relationship between pairs of elements which is not
necessarily hierarchical in nature. For example, suppose an airline flies only between the cities
connected by lines in Fig. The data structure which reflects this type of relationship is called a
graph.

7
DATA STRUCTURES OPERATIONS
The data appearing in data structures are processed by means of certain operations.
The following four operations play a major role in this text:
1. Traversing: accessing each record/node exactly once so that certain items in the record
may be processed. (This accessing and processing is sometimes called “visiting” the
record.)
2. Searching: Finding the location of the desired node with a given key value, or finding
the locations of all such nodes which satisfy one or more conditions.
3. Inserting: Adding a new node/record to the structure.

4. Deleting: Removing a node/record from the structure.

The following two operations, which are used in special situations:

1. Sorting: Arranging the records in some logical order (e.g., alphabetically according to
some NAME key, or in numerical order according to some NUMBER key, such as social
security number or account number)
2. Merging: Combining the records in two different sorted files into a single sorted file.

ARRAYS

• An Array is defined as, an ordered set of similar data items. All the data items
of anarray are stored in consecutive memory locations.
• The data items of an array are of same type and each data items can be
accessed using the same name but different index value.
• An array is a set of pairs, <index, value >, such that each index has a value
associatedwith it. It can be called as corresponding or a mapping
Ex: <index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35
Here, list is the name of array. By using, list [0] to list [4] the data items in list can be

8
 accessed.

Array in C

Declaration: A one dimensional array in C is declared by adding brackets to the name of a

variable.

Ex: int list[5], *plist[5];

The array list[5], defines 5 integers and in C array start at index 0, so list[0], list[1],
list[2], list[3], list[4] are the names of five array elements which contains an integer
value.

The array *plist[5], defines an array of 5 pointers to integers. Where, plist[0],
plist[1], plist[2], plist[3], plist[4] are the five array elements which contains a pointer
to an integer.

Implementation:

• When the complier encounters an array declaration, list[5], it allocates five consecutive
memory locations. Each memory is enough large to hold a single integer.
• The address of first element of an array is called Base Address. Ex: For list[5]
theaddress of list[0] is called the base address.
• If the memory address of list[i] need to compute by the compiler, then the size of the
int would get by sizeof (int), then memory address of list[i] is as follows:

list[i] = α + i * sizeof (int)

9
 Where, α is base address.

Difference between int *list1; & int list2[5];

The variables list1 and list2 are both pointers to an int, but in list2[5] five memory
locations are reserved for holding integers. list2 is a pointer to list2[0] and list2+i is a
pointer to list2[i].

Note: In C the offset i do not multiply with the size of the type to get to the appropriate
element of the array. Hence (list2+i) is equal &list2[i] and *(list2+i) is equal to list2[i].

How C treats an array when it is parameter to a function?

• All parameters of a C functions must be declared within the function. As various

parameters are passed to functions, the name of an array can be passed as
parameter.
• The range of a one-dimensional array is defined only in the main function
since newstorage for an array is not allocated within a function.
• If the size of a one dimensional array is needed, it must be passed into
function as aargument or accessed as a global variable.

Example: Array Program

#define MAX_SIZE 100

float sum(float [], int);
float input[MAX_SIZE], answer;

10
void main(void)
{
int i;
for( i=0; i<MAX_SIZE; i++)
input[i]= i;
answer = sum(input, MAX_SIZE);
printf(“\n The sum is: %f \n”,answer);
}

float sum(float list[], int n)

{
int i;
float tempsum = 0;for(i=0; i<n;i++)
tempsum = tempsum + list[i];
return tempsum;
}

When sum is invoked, input=&input[0] is copied into a temporary location and

associatedwith the formal parameter list

A function that prints out both the address of the ith element of the array and the value
found at that address can written as shown in below program.

void print1 (int *ptr, int rows)

{
int i;
printf(“ Address contents \n”);
for(i=0; i<rows; i++)
printf(“% 8u %5d \n”, ptr+i, *(prt+i));
printf(“\n”);
}

11
 Output:
Address Content
12244868 0
12344872 1
12344876 2
12344880 3
12344884 4

STRUCTURES
In C, a way to group data that permits the data to vary in type. This mechanism is called the
structure, for short struct.

A structure (a record) is a collection of data items, where each item is identified as to its
type and name.

Syntax: struct

{ data_type member 1;
data_type member 2;

………………………

………………………

data_type member n;
} variable_name;

Ex: struct {
char
name[10];int
age;
float salary;
12
 } Person;
The above example creates a structure and variable name is Person and that has three fields:
name = a name that is a character array
age = an integer value representing the age of the person
salary = a float value representing the salary of the individual

Assign values to fields

To assign values to the fields, use . (dot) as the structure member operator. This operator
is used to select a particular member of the structure

Ex: strcpy(Person.name,“james”);
Person.age = 10;
Person.salary = 35000;

Type-Defined Structure

The structure definition associated with keyword typedef is called Type-Defined Structure.
Syntax 1: typedef struct

data_type member 1;

data_type member 2;

………………………

………………………

data_type member n;

}Type_name;

13
 Where,
• typedef is the keyword used at the beginning of the definition and by using
typedefuser defined data type can be obtained.
• struct is the keyword which tells structure is defined to the complier
• The members are declare with their data_type
• Type_name is not a variable, it is user defined data_type.

Syntax 2: struct struct_name

data_type member 1;

data_type member 2;

………………………

………………………

data_type member n;

};

typedef struct struct_name Type_name;

Ex: typedef struct{

char
name[10];int
age;
float salary;

14
 }humanBeing;

In above example, humanBeing is the name of the type and it is a user defined data type.
Declarations of structure variables:
humanBeing person1, person2;

This statement declares the variable person1 and person2 are of type humanBeing.

Structure Operation

The various operations can be performed on structures and structure members.

1. Structure Equality Check:

Here, the equality or inequality check of two structure variable of same type or dissimilar
typeis not allowed

typedef struct{

char
name[10];int
age;
float salary;
}humanBeing;
humanBeing person1, person2;

if (person1 = = person2) is invalid.

#define FALSE 0

#define TRUE 1
if (humansEqual(person1,person2))
printf("The two human beings are the same\n");
else
printf("The two human beings are not the same\n");
15
 int humansEqual(humanBeing person1, humanBeing person2)
{ /* return TRUE if person1 and person2 are the same human being otherwise
return FALSE */
if (strcmp(person1.name, person2.name))
return FALSE;
if (person1.age != person2.age)
return FALSE;
if (person1.salary !=
person2.salary) return
FALSE;
return TRUE;
}

2. Assignment operation on Structure variables:

person1 = person2

The above statement means that the value of every field of the structure of person 2 is
assigned as the value of the corresponding field of person 1, but this is invalid
statement.

Valid Statements is given below:

strcpy(person1.name, person2.name);
person1.age = person2.age;
person1.salary = person2.salary;

Structure within a structure:

There is possibility to embed a structure within a structure. There are 2 ways to embed
structure.

1. The structures are defined separately and a variable of structure type is declared inside the

16
 definition of another structure. The accessing of the variable of a structure type that are
nestedinside another structure in the same way as accessing other member of that structure

Example: The following example shows two structures, where both the structure are defined
separately.
typedef struct{
{
int month;
int day;
int year;
}
char name[10];int age;
float salary;date dob;
} humanBeing;humanBeing person1;

A person born on February 11, 1944, would have the values for the date struct set as:
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

2. The complete definition of a structure is placed inside the definition of another structure.

Example:

typedef struct {
char
name[10];int
age;
float
salary;
struct {
int month;
int day;

17
 int year;
} date;
} humanBeing

SELF-REFERENTIAL STRUCTURES
A self-referential structure is one in which one or more of its components is a pointer to itself.
Self-referential structures usually require dynamic storage management routines (malloc and
free) to explicitly obtain and release memory.

Consider as an example:
typedef struct {
char data;
struct list *link ;
} list;

18
Each instance of the structure list will have two components data and link.

• Data: is a single character,

• Link: link is a pointer to a list structure. The value of link is either the address
in memory of an instance of list or the null pointer.

Consider these statements, which create three structures and assign values to their respective
fields:

list item1, item2, item3;

item1.data = 'a';
item2.data = 'b';
item3.data = 'c';
item1.link = item2.1ink = item3.link = NULL;

Structures item1, item2 and item3 each contain the data item a, b, and c respectively, and the
null pointer. These structures can be attached together by replacing the null link field in
item2 with one that points to item 3 and by replacing the null link field in item 1 with one that
points to item 2.

item1.link = &item2;
item2.1ink =
&item3;

Unions:
A union is similar to a structure, it is collection of data similar data type or dissimilar.

19
 Syntax: union {{{
data_type member 1;
{
data_type member 2;

………………………

data_type member n;

Example: }variable_name;

union{
int
children;int
} u; beard;

Union Declaration:

A union declaration is similar to a structure, but the fields of a union must share their
memoryspace. This means that only one field of the union is "active" at any given time.

union
{ char name;
int age;
float
salary;
}u;

20
The major difference between a union and a structure is that unlike structure members which
are stored in separate memory locations, all the members of union must share the same memory
space. This means that only one field of the union is "active" at any given time.
Example:
#include
<stdio.h>union
job {

char
name[32];
float salary;
int worker_no;
}u;
int main( ){
printf("Enter name:\n");
scanf("%s", &u.name);
printf("Enter salary: \n");
scanf("%f", &u.salary);
printf("Displaying\n Name :%s\n",u.name);
printf("Salary: %.1f",u.salary);
return 0;

21
Output:

Enter name: Albert

Enter salary:
45678.90

Displaying
Name: f%gupad (Garbage
Value)Salary: 45678.90

POINTERS
A pointer is a variable which contains the address in memory of another variable.
The two most important operator used with the pointer type are
& - The unary operator & which gives the address of a variable
* - The indirection or dereference operator * gives the content of the object pointed
to by a pointer.

Declaration

int i, *pi;

Here, i is the integer variable and pi is a pointer to an integer

pi = &i;
Here, &i returns the address of i and assigns it as the value of pi

Null Pointer

The null pointer points to no object or

function. The null pointer is represented by the
integer 0.
The null pointer can be used in relational expression, where it is interpreted as
false. Ex: if (pi = = NULL) or if (!pi)

22
Pointers can be Dangerous:

Pointer can be very dangerous if they are misused. The pointers are dangerous in
following situations:

1. Pointer can be dangerous when an attempt is made to access an area of memory that is
either out of range of program or that does not contain a pointer reference to a legitimate
object.

Ex: main ()

{
int *p;
int pa = 10;
p = &pa;
printf(“%d”, *p); //output = 10;
printf(“%d”, *(p+1)); //accessing memory which is out of range
}
2. It is dangerous when a NULL pointer is de-referenced, because on some computer it may
return 0 and permitting execution to continue, or it may return the result stored in location zero,
so it may produce a serious error.

3. Pointer is dangerous when use of explicit type casts in converting between pointer types

Ex: pi = malloc (sizeof

(int));pf = (float*) pi;

4. In some system, pointers have the same size as type int, since int is the default type specifier,
some programmers omit the return type when defining a function. The return type defaults to
int which can later be interpreted as a pointer. This has proven to be a dangerous practice on
some computer and the programmer is made to define explicit types for functions.

23
Pointers to Pointers

A variable which contains address of a pointer variable is called pointer-to-pointer.

REPRESENTATION OF LINEAR ARRAYS IN MEMORY

Linear Array

A linear array is a list of a finite number ‘n’ of homogeneous data element such that
a. The elements of the array are reference respectively by an index set consisting of
n consecutive numbers.
b. The element of the array are respectively in successive memory locations.

The number n of elements is called the length or size of the array. The length or the
numbers of elements of the array can be obtained from the index set by the formula
When LB = 0,
When LB = 1, Where,

Length = UB – LB + 1 Length = UB

UB is the largest index called the Upper Bound

LB is the smallest index, called the Lower
Bound

Representation of linear arrays in memory

Let LA be a linear array in the memory of the computer. The memory of the computer is
simply a sequence of address location as shown below,

24
 The elements of LA are stored in successive memory cells. The computer does not keep
track of the address of every element of LA, but needs to keep track only the address of the
first element of LA denoted by,
Base (LA)

and called the base address of LA. Using the base address of LA, the computer calculates the
address of any element of LA bythe formula

LOC (LA[K]) = Base(LA) + w(K – lower bound)

Where, w is the number of words per memory cell for the array LA.

DYNAMICALLY ALLOCATED ARRAYS

One Dimensional Array

While writing computer programs, if finds ourselves in a situation where we cannot

determinehow large an array to use, then a good solution to this problem is to defer this
decision to run time and allocate the array when we have a good estimate of the required
array size.

Example:

int i, n, *list;
printf(“Enter the number of numbers to generate:”);
scanf(“%d”, &n);
if(n<1)
{
fprintf (stderr, “Improper value of n \n”);
exit(EXIT_FAILURE);
}

MALLOC (list, n*sizeof(int));

The programs fails only when n<1 or insufficient memory to hold the list of numbers that
areto be sorted.
25
Two Dimensional Arrays

C uses array-of-arrays representation to represent a multidimensional array. The two

dimensional arrays is represented as a one-dimensional array in which each element is itself
aone-dimensional array.

Example: int x[3][5];

Array-of-arrays representation

C find element x[i][j] by first accessing the pointer in x[i].

Where x[i] = α+ i* sizeof(int), which give the address of the zeroth element of row i of
thearray.

Then adding j*sizeof(int) to this pointer ( x[i] ) , the address of the [j]th element of row i is

determined.

x[i] = α+ i*
sizeof(int)x[j] = α+ j*
sizeof(int)

x[i][j] = x[i]+ i* sizeof(int)

Creation of Two-Dimensional Array Dynamically

int **myArray;
myArray = make2dArray(5,10);
myArray[2][4]=6;

int ** make2dArray(int rows, int cols)

{ /* create a two dimensional rows X cols array */
int **x, i;
26
 MALLOC(x, rows * sizeof (*x)); /*get memory for row
pointers*/for (i= 0;i<rows; i++) /* get memory for each row */
MALLOC(x[i], cols * sizeof(**x));
return x;
}

The second line allocates memory for a 5 by 10 two-dimensional array of integers and the
third line assigns the value 6 to the [2][4] element of this array.

BASIC OPERATIONS

1. Traversing
• Let A be a collection of data elements stored in the memory of the computer.
Supposeif the contents of the each elements of array A needs to be printed or to
count the numbers of elements of A with a given property can be accomplished by
Traversing.
• Traversing is a accessing and processing each element in the array exactly once.

Algorithm 1: (Traversing a Linear Array)

Hear LA is a linear array with the lower bound LB and upper bound UB. This algorithm
traverses LA applying an operation PROCESS to each element of LA using while loop.
1. [Initialize Counter] set K:= LB
2. Repeat step 3 and 4 while K ≤ UB
3. [Visit element] Apply PROCESS to LA [K]
4. [Increase counter] Set K:= K +
1 [End of step 2 loop]
5. Exit

Algorithm 2: (Traversing a Linear Array)

Hear LA is a linear array with the lower bound LB and upper bound UB. This algorithm
traverses LA applying an operation PROCESS to each element of LA using repeat – for
loop.
27
 1. Repeat for K = LB to UB

Apply PROCESS to LA
[K][End of loop]
2. Exit.

Example:

Consider the array AUTO which records the number of automobiles sold each year from
1932 through 1984.

To find the number NUM of years during which more than 300 automobiles were sold,
involves traversing AUTO.
1. [Initialization step.] Set NUM := 0
2. Repeat for K = 1932 to 1984:
If AUTO [K] > 300, then: Set NUM: = NUM + 1.
[End of loop.]
Return.
2. Inserting
• Let A be a collection of data elements stored in the memory of the computer.
Inserting refers to the operation of adding another element to the collection
A.
• Inserting an element at the “end” of the linear array can be easily done provided the
memory space allocated for the array is large enough to accommodate the additional
element.
• Inserting an element in the middle of the array, then on average, half of the elements
must be moved downwards to new locations to accommodate the new element and keep
the order of the other elements.

Algorithm:

INSERT (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such that K ≤ N. This

28
 algorithm inserts an element ITEM into the Kth position in LA.

1. [Initialize counter] set J:= N

2. Repeat step 3 and 4 while J ≥ K

3. [Move Jth element downward] Set LA [J+1] := LA[J]

4. [Decrease counter] set J:= J –
1 [End of step 2 loop]
5. [Insert element] set LA[K]:= ITEM
6. [Reset N] set N:= N+1
7. Exit

3. Deleting
• Deleting refers to the operation of removing one element to the collection A.

• Deleting an element at the “end” of the linear array can be easily done with
difficulties.

• If element at the middle of the array needs to be deleted, then each

subsequentelements be moved one location upward to fill up the array.

Algorithm

DELETE (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such that K ≤ N. this

algorithm deletes the Kth element from LA

1. Set ITEM:= LA[K]

2. Repeat for J = K to N – 1

[Move J + 1 element upward] set LA[J]:=

LA[J+1][End of loop]
3. [Reset the number N of elements in LA] set N:= N – 1

4. Exit

29
Example: Inserting and Deleting

Suppose NAME is an 8-element linear array, and suppose five names are in the array,
as in Fig.(a). Observe that the names are listed alphabetically, and suppose we want to
keep the array names alphabetical at all times. Suppose Ford is added to the array. Then
Johnson, Smith and Wagner must each be moved downward one location, as in Fig.(b).
Next suppose Taylor is added to the array; then Wagner must be moved, as in Fig.(c).
Last, suppose Davis is removed from the array. Then the five names Ford, Johnson,
Smith, Taylor and Wagner must each be moved upward one location, as in Fig.(d).

4. Sorting
Sorting refers to the operation of rearranging the elements of a list. Here list be a set
of nelements. The elements are arranged in increasing or decreasing order.

Ex: suppose A is the list of n numbers. Sorting A refers to the operation of

rearranging theelements of A so they are in increasing order, i.e., so that,
 A[I] < A[2] < A[3] < ... < A[N]

For example, suppose A originally is the list

8, 4, 19, 2, 7, 13, 5, 16
After sorting, A
is the list
2, 4, 5, 7, 8, 13, 16, 19

Asymptotic Notations

When it comes to analysing the complexity of any algorithm in terms of time and space,
we can never provide an exact number to define the time required and the space required
by the algorithm, instead we express it using some standard notations, also known
as Asymptotic Notations.

When we analyse any algorithm, we generally get a formula to represent the amount of
time required for execution or the time required by the computer to run the lines of code of
the algorithm, number of memory accesses, number of comparisons, temporary variables
occupying memory space etc. This formula often contains unimportant details that don't
really tell us anything about the running time.

Let us take an example, if some algorithm has a time complexity of T(n) = (n2 + 3n + 4),
which is a quadratic equation. For large values of n, the 3n + 4 part will become
insignificant compared to the n2 part.
For n = 1000, n2 will be 1000000 while 3n + 4 will be 3004.

Also, When we compare the execution times of two algorithms the constant coefficients of
higher order terms are also neglected.

An algorithm that takes a time of 200n2 will be faster than some other algorithm that
takes n3 time, for any value of n larger than 200. Since we're only interested in the
asymptotic behavior of the growth of the function, the constant factor can be ignored too.

What is Asymptotic Behaviour

The word Asymptotic means approaching a value or curve arbitrarily closely (i.e., as some
sort of limit is taken).

Remember studying about Limits in High School, this is the same.

The only difference being, here we do not have to find the value of any expression
where n is approaching any finite number or infinity, but in case of Asymptotic notations,
we use the same model to ignore the constant factors and insignificant parts of an
expression, to device a better way of representing complexities of algorithms, in a single
coefficient, so that comparison between algorithms can be done easily.
Let's take an example to understand this:

If we have two algorithms with the following expressions representing the time required
by them for execution, then:

Expression 1: (20n2 + 3n - 4)

Expression 2: (n3 + 100n - 2)

Now, as per asymptotic notations, we should just worry about how the function will grow
as the value of n(input) will grow, and that will entirely depend on n2 for the Expression 1,
and on n3 for Expression 2. Hence, we can clearly say that the algorithm for which running
time is represented by the Expression 2, will grow faster than the other one, simply by
analysing the highest power coeeficient and ignoring the other constants(20 in 20n2) and
insignificant parts of the expression(3n - 4 and 100n - 2).

The main idea behind casting aside the less important part is to make things manageable.

All we need to do is, first analyse the algorithm to find out an expression to define it's time
requirements and then analyse how that expression will grow as the input(n) will grow.

Types of Asymptotic Notations

We use three types of asymptotic notations to represent the growth of any algorithm, as
input increases:

1. Big Theta (Θ)

2. Big Oh(O)

3. Big Omega (Ω)

Tight Bounds: Theta

When we say tight bounds, we mean that the time compexity represented by the Big-Θ
notation is like the average value or range within which the actual time of execution of the
algorithm will be.

For example, if for some algorithm the time complexity is represented by the expression
3n2 + 5n, and we use the Big-Θ notation to represent this, then the time complexity would
be Θ(n2), ignoring the constant coefficient and removing the insignificant part, which is
5n.

Here, in the example above, complexity of Θ(n2) means, that the average time for any
input n will remain in between, k1 * n2 and k2 * n2, where k1, k2 are two constants, therby
tightly binding the expression representing the growth of the algorithm.

Upper Bounds: Big-O

This notation is known as the upper bound of the algorithm, or a Worst Case of an
algorithm.

It tells us that a certain function will never exceed a specified time for any value of input n.

The question is why we need this representation when we already have the big-Θ notation,
which represents the tightly bound running time for any algorithm. Let's take a small
example to understand this.
Consider Linear Search algorithm, in which we traverse an array elements, one by one to
search a given number.

In Worst case, starting from the front of the array, we find the element or number we are
searching for at the end, which will lead to a time complexity of n, where n represents the
number of total elements. But it can happen, that the element that we are searching for is
the first element of the array, in which case the time complexity will be 1.

Now in this case, saying that the big-Θ or tight bound time complexity for Linear search is
Θ(n), will mean that the time required will always be related to n, as this is the right way
to represent the average time complexity, but when we use the big-O notation, we mean to
say that the time complexity is O(n), which means that the time complexity will never
exceed n, defining the upper bound, hence saying that it can be less than or equal to n,
which is the correct representation.

This is the reason, most of the time you will see Big-O notation being used to represent the
time complexity of any algorithm, because it makes more sense.

Lower Bounds: Omega

Big Omega notation is used to define the lower bound of any algorithm or we can say the
best case of any algorithm.

This always indicates the minimum time required for any algorithm for all input values,
therefore the best case of any algorithm.

In simple words, when we represent a time complexity for any algorithm in the form of
big-Ω, we mean that the algorithm will take atleast this much time to cmplete it's execution.
It can definitely take more time than this too.
Recursion:

Some computer programming languages allow a module or function to call itself. This
technique is known as recursion. In recursion, a function α either calls itself directly or
calls a function β that in turn calls the original function α. The function α is called recursive
function.

Example − a function calling itself.

int function(int value) {

if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}

Example − a function that calls another function which in turn calls it again.

int function1(int value1) {

if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}

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.

Mechanism of Execution:
• When a recursive program is executed, the recursive
function calls are not executed immediately.
• They are kept aside (on a stack) until the stopping condition is encountered.
• The function calls are then executed in reverse order.

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.

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

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.
Example 1: Sum of Natural Numbers Using Recursion
#include
<stdio.h>
#include
<conio.h>
int
sum(int);
void main()
{
int number,
result;
printf("Enter
a positive
integer: ");
scanf("%d",
&number);
result =
sum(number);
printf("sum =
%d", result);
return 0;
}
int sum(int n)
{
if (n != 0)
return n +
sum(n-1); else
 return n;
}

Example 2: Write a recursive function to calculate the factorial value of given number.
#include<stdio.h>
#include<conio.h>
int fact (int);
void main()
{
int x,y;
clrscr();
printf("Enter any number\n"); scanf("%d",&x);
y=fact(x);
printf("Factorial value of given number===%d",y);
getch();
}
int fact (int n)
{
int
f=1;
if(n
==1
)
retu
rn(1
);
else
f=n*fact(
n-1);
 return (f);
}

Example 3: Write a recursive function to check any number is Prime or not.

#include<std
io.h>
#include<co
nio.h>
int prime
(int);
main()
{
int no,i;
printf("enter any number");
scanf("%d",&no);
i=prime(no);
if(i==1)
printf("Prime
Number"); else
printf("Not Prime Number");
getch();
}
int prime (int n)
{
static int x=2;
if(x==n)
return(1);
if(n%x==0)
 return(0);
else
{
x++;
prime(n);
}
}

Example 4: Write a recursive function print the Fibonacci series.

#include<stdio.h>
#include<stdio.h>
int Fibonacci(int);
void main()
{
int n, i = 0, c; scanf("%d",&n);
printf("Fibonacci series\n");
for ( c = 1 ; c <= n ; c++ )
{
printf("%d\n",
fibonacci(i)); i++;
}
getch();
}
int Fibonacci(int n)
{
if ( n == 0 ) return 0;
else if ( n == 1 )
return 1;
 else
return ( Fibonacci(n-1) + Fibonacci(n-2) );
}

Searching-

• Searching is a process of finding a particular element among several given elements.

• The search is successful if the required element is found.
• Otherwise, the search is unsuccessful.

Searching Algorithms-
Searching Algorithms are a family of algorithms used for the purpose of searching.

The searching of an element in the given array may be carried out in the following two
ways-

Linear Search-
• Linear Search is the simplest searching algorithm.
• It traverses the array sequentially to locate the required element.
• It searches for an element by comparing it with each element of the array one by one.
• So, it is also called as Sequential Search.
 Linear Search Algorithm is applied when-

• No information is given about the array.

• The given array is unsorted or the elements are unordered.
• The list of data items is smaller.

Linear Search Algorithm-

Consider-

• There is a linear array ‘a’ of size ‘n’.

• Linear search algorithm is being used to search an element ‘item’ in this linear array.
• If search ends in success, it sets loc to the index of the element otherwise it sets loc to -
1.

Then, Linear Search Algorithm is as follows-

Linear_Search (a , n , item , loc)

Begin

for i = 0 to (n - 1) by 1 do
if (a[i] = item) then
set loc = i
Exit
endif
endfor
set loc = -1
End
 Time Complexity Analysis-

Linear Search time complexity analysis is done below-

Best case-

In the best possible case,

• The element being searched may be found at the first position.

• In this case, the search terminates in success with just one comparison.
• Thus in best case, linear search algorithm takes O(1) operations.
Worst Case-
In the worst possible case,

• The element being searched may be present at the last position or not present in the array
at all.
• In the former case, the search terminates in success with n comparisons.
• In the later case, the search terminates in failure with n comparisons.
• Thus in worst case, linear search algorithm takes O(n) operations.

Thus, Time Complexity of Linear Search Algorithm is O(n).

Here, n is the number of elements in the linear array.

Linear Search Efficiency-

• Linear Search is less efficient when compared with other algorithms like Binary Search
& Hash tables.
• The other algorithms allow significantly faster searching.
 Linear Search Example-
Consider-

• We are given the following linear array.

• Element 15 has to be searched in it using Linear Search Algorithm.

Now,

• Linear Search algorithm compares element 15 with all the elements of the array one by
one.
• It continues searching until either the element 15 is found or all the elements are
searched.
Linear Search Algorithm works in the following steps-

Step-01:

It compares element 15 with the 1st element 92.

• Since 15 ≠ 92, so required element is not found.

• So, it moves to the next element.
Step-02:

It compares element 15 with the 2nd element 87.

• Since 15 ≠ 87, so required element is not found.

• So, it moves to the next element.
 Step-03:

It compares element 15 with the 3rd element 53.

• Since 15 ≠ 53, so required element is not found.

• So, it moves to the next element.
Step-04:

It compares element 15 with the 4th element 10.

• Since 15 ≠ 10, so required element is not found.

• So, it moves to the next element.
Step-05:

It compares element 15 with the 5th element 15.

• Since 15 = 15, so required element is found.

• Now, it stops the comparison and returns index 4 at which element 15 is present.

Binary Search-

• Binary Search is one of the fastest searching algorithms.

• It is used for finding the location of an element in a linear array.
• It works on the principle of divide and conquer technique.

Binary Search Algorithm can be applied only on Sorted arrays. So, the elements must be
arranged in-

• Either ascending order if the elements are numbers.

• Or dictionary order if the elements are strings.
 To apply binary search on an unsorted array,

• First, sort the array using some sorting technique.

• Then, use binary search algorithm.

Binary Search Algorithm-

Consider-

• There is a linear array ‘a’ of size ‘n’.

• Binary search algorithm is being used to search an element ‘item’ in this linear array.
• If search ends in success, it sets loc to the index of the element otherwise it sets loc to -
1.
• Variables beg and end keeps track of the index of the first and last element of the array
or sub array in which the element is being searched at that instant.
• Variable mid keeps track of the index of the middle element of that array or sub array in
which the element is being searched at that instant.

Then, Binary Search Algorithm is as follows-

Begin

Set beg = 0
Set end = n-1
Set mid = (beg + end) / 2
while ( (beg <= end) and (a[mid] ≠ item) ) do
if (item < a[mid]) then
Set end = mid - 1
else
 Set beg = mid + 1
endif
Set mid = (beg + end) / 2
endwhile
if (beg > end) then
Set loc = -1
else
Set loc = mid
endif
End

Time Complexity Analysis-

Binary Search time complexity analysis is done below-

• In each iteration or in each recursive call, the search gets reduced to half of the array.
• So for n elements in the array, there are log2n iterations or recursive calls.

Thus, Time Complexity of Binary Search Algorithm is O(log2n).

Here, n is the number of elements in the sorted linear array.

This time complexity of binary search remains unchanged irrespective of the element
position even if it is not present in the array.

Binary Search Algorithm searches an element by comparing it with the middle most
element of the array.

Then, following three cases are possible-

Case-01:
If the element being searched is found to be the middle most element, its index is returned.
 Case-02:

If the element being searched is found to be greater than the middle most element, then its
search is further continued in the right sub array of the middle most element.

Case-03
If the element being searched is found to be smaller than the middle most element, then its
search is further continued in the left sub array of the middle most element.

This iteration keeps on repeating on the sub arrays until the desired element is found or
size of the sub array reduces to zero.

Binary Search Example-

Consider-

• We are given the following sorted linear array.

• Element 15 has to be searched in it using Binary Search Algorithm.

Binary Search Algorithm works in the following steps-

Step-01:

• To begin with, we take beg=0 and end=6.

• We compute location of the middle element as-
mid
 = (beg + end) / 2

= (0 + 6) / 2

=3

• Here, a[mid] = a[3] = 20 ≠ 15 and beg < end.

• So, we start next iteration.
Step-02:

Since a[mid] = 20 > 15, so we take end = mid – 1 = 3 – 1 = 2 whereas beg remains
unchanged.

• We compute location of the middle element as-mid

= (beg + end) / 2

= (0 + 2) / 2

=1

• Here, a[mid] = a[1] = 10 ≠ 15 and beg < end.

• So, we start next iteration.
Step-03:

Since a[mid] = 10 < 15, so we take beg = mid + 1 = 1 + 1 = 2 whereas end remains
unchanged.

• We compute location of the middle element as-mid

= (beg + end) / 2

= (2 + 2) / 2

=2

• Here, a[mid] = a[2] = 15 which matches to the element being searched.

• So, our search terminates in success and index 2 is returned.

Binary Search Algorithm Advantages-

The advantages of binary search algorithm are-

• It eliminates half of the list from further searching by using the result of each comparison.
• It indicates whether the element being searched is before or after the current position in
the list.
• This information is used to narrow the search.
• For large lists of data, it works significantly better than linear search.
Binary Search Algorithm Disadvantages-

The disadvantages of binary search algorithm are-

• It employs recursive approach which requires more stack space.

• Programming binary search algorithm is error prone and difficult.
• The interaction of binary search with memory hierarchy i.e. caching is poor.

For in-memory searching, if the interval to be searched is small,

• Linear search may exhibit better performance than binary search.

• This is because it exhibits better locality of reference.

+++++