1

21CSC201J – DATA STRUCTURES AND ALGORITHMS

Unit-1
Introduction
Programming in C - Primitive data types, Structures, Self-referential structures, Pointers and
structures, Dynamic memory allocation, Matrix multiplication; Data Structure – Definition,
Types, ADT, Operations; Mathematical notations - Big O, Omega and Theta, Complexity –
Time, Space, Trade off.

1. Introduction: Programming in C
• To learn about the structure of C program
• To learn about the primitive data types
• Understanding the Structure of a C Program
• Familiarity with Primitive Data Types

• C is a structured programming language. It is also known as function orientated

programming language. C programming language was developed in the year
of 1972 by Dennis Ritchie at Bell Laboratories in the USA (AT & T). In the year of 1968,
research was started by Dennis Ritchie on programming languages like BCPL, CPL.
• The main aim of his research was to develop a new language to create an OS called
UNIX. After four years of research, a new programming language was created with
solutions for drawbacks in languages like BCPL & CPL. In the year of 1972, the new
language was introduced with the name “Traditional C”.
• The name 'C' was selected from the sequence of previous language ‘B’ (BCPL) because
most of the features of 'c' were derived from BCPL (B language).
• The first outcome of the C language was the UNIX operating system. The initial UNIX
OS was completely developed using 'C' programming language.
• The C programming language is very popular because it is reliable, simple and easy to
use and it is the base for almost all the other programming languages.

Structure of a C program

CODING GEEKZ (Dr.S.Priya)

 2

Comments:

• The comment lines are simply ignored by the compiler, that means they are not
executed. In C, there are two types of comments.

1. Single Line Comments: Single line comment begins with // symbol. We can write any
number of single line comments.
2. Multiple Lines Comments: Multiple lines comment begins with /* symbol and ends
with */. We can write any number of multiple lines comments in a program.

• In a C program, the comment lines are optional.

Preprocessing Commands

• Preprocessing commands are used to include header files and to define constants.
• #include statement to include the header file into our program.
• #define statement to define a constant. The preprocessing statements are used
according to the requirements

Global Declaration

• The global declaration is used to define the global variables, which are common
for all the functions after its declaration.

int main()

• main is a user-defined method which tells the compiler that this is the starting
point of the program execution.

• Here, int is a data type of a value that is going to return to the Operating System
after completing the main method execution. If we don't want to return any value,
we can use it as void.

Open Brace ( { )

• The open brace indicates the beginning of the block which belongs to the main
method. In C program, every block begins with a '{' symbol.

Local Declaration

• In this section, we declare the variables and functions that are local to the function or
block in which they are declared. The variables which are declared in this section are
valid only within the function or block in which they are declared.

Executable statements

• In this section, we write the statements which perform tasks like reading data,
displaying the result, calculations, etc., All the statements in this section are written
according to the requirements.

CODING GEEKZ (Dr.S.Priya)

 3

Closing Brace ( } )

• The close brace indicates the end of the block which belongs to the main method. In
C program every block ends with a '}' symbol.

User-defined function()

• The user-defined function implementation can also be performed before the main
method. Every user-defined function needs a function call to execute its statements.

General rules for any C program

1. Every executable statement must end with a semicolon symbol (;).

2. Every C program must contain exactly one main method (Starting point of the program
execution).
3. All the system-defined words (keywords) must be used in lowercase letters.
4. Keywords cannot be used as user-defined names(identifiers).
5. For every open brace ({), there must be respective closing brace (}).
6. Every variable must be declared before it is used.

Example of C Program

Identifiers

• One feature present in all computer languages is the identifier. Identifiers allow us to
name data and other objects in the program. Each identified object in the computer
is stored at a unique address.
• Rules for Identifiers:

• Examples of Valid and Invalid identifiers:

CODING GEEKZ (Dr.S.Priya)

 4

Keywords

• Keywords are system defined identifiers. Keywords are reserved words of the
language. They have specific meaning in the language and cannot be used by the
programmer as variable or constant names.
• There are 32 Keywords in C Programming.

Figure: Keywords Figure: Variables

Variables

• Variables are named memory locations that have a type, such as integer or
character, which is inherited from their type.
• The type determines the values that a variable may contain and the operations
that may be used with its values.

Figure : Examples of Variable Declarations

CODING GEEKZ (Dr.S.Priya)

 5

Figure: Examples of Variable Initialization

Constants

• Constants are data values that cannot be changed during the execution of a
program. eg. const double PI = 3.14
• Here, PI is a constant. Basically, what it means is that, PI and 3.14 is same for this
program.

Integer constants

• A integer constant is a numeric constant (associated with number) without any

fractional or exponential part.
• There are three types of integer constants in C programming:

▪ decimal constant(base 10)

▪ octal constant(base 8)
▪ hexadecimal constant(base 16)

Floating-point constants

• A floating point constant is a numeric constant that has either a fractional form
or an exponent form.
• For example: 2.0,0.0000234,-0.22E-5

Character constants

• A character constant is a constant which uses single quotation around

characters. For example: 'a', 'l', 'm', 'F'

String constants

• String constants are the constants which are enclosed in a pair of double-quote
marks.
• For example: "good" ,"x","Earth is round\n"

Escape Sequences

CODING GEEKZ (Dr.S.Priya)

 6

• Sometimes, it is necessary to use characters which cannot be typed or has special

meaning in C programming.
• For example: newline(enter), tab, question mark etc. In order to use these characters,
escape sequence is used.

Sequences Character

\b Backspace
\f Form feed
\n Newline
\r Return
\t Horizontal tab
\v Vertical tab
\\ Backslash
\' Single quotation mark
\" Double quotation mark
\? Question mark
\0 Null character

2.Primitive data types

• Each variable in C has an associated data type. It specifies the type of data that
the variable can store like integer, character, floating, double, etc.
• Each data type requires different amounts of memory and has some specific
operations which can be performed over it.

Figure: Datatypes in C

Integer Data Type

• The integer datatype in C is used to store the whole numbers without decimal values.
Octal values, hexadecimal values, and decimal values can be stored in int data type in
C.
• Range: -2,147,483,648 to 2,147,483,647
• Size: 4 bytes
• Format Specifier: %d
• sizeof (short) ≤ sizeof (int) ≤ sizeof (long) ≤ sizeof (long long)

CODING GEEKZ (Dr.S.Priya)

 7

Figure: Integer Types

Typical Integer Sizes and Values for Signed Integers:

Float Data Type

• Float in C is used to store decimal and exponential values. It is used to store

decimal numbers (numbers with floating point values) with single precision.
• Range: 1.2E-38 to 3.4E+38
• Size: 4 bytes
• Format Specifier: %f
• sizeof (float) ≤ sizeof (double) ≤ sizeof (long double)

Figure: Floating Point Types

Void Data Types

• The void data type in C is used to specify that no value is present. It does not
provide a result value to its caller.
• It has no values and no operations. It is used to represent nothing.
• Void is used in multiple ways as function return type, function arguments as void
etc.

CODING GEEKZ (Dr.S.Priya)

 8

Size of Data Types in C

• The size of the data types in C is dependent on the size of the architecture, so we
cannot define the universal size of the data types.

• For that, the C language provides the sizeof() operator to check the size of the data
types.

3. Structures
• Structure is a collection of logically related data items of different datatypes
grouped together under single name. Structure is a user defined datatype.
• Structure helps to build a complex datatype which is more meaningful than an
array. But, an array holds similar datatype record, when structure holds different
datatypes records.
• Two fundamental aspects of Structure:
o Declaration of Structure Variable
o Accessing of Structure Member
Example to Define Structure

• You must terminate structure definition with semicolon ;.

• You cannot assign value to members inside the structure definition, it will cause
compilation error.

CODING GEEKZ (Dr.S.Priya)

 9

Create Structure variable

• A data type defines various properties about data stored in memory.

• To use any data type we must declare its variable.
• Hence, let us learn how to create our custom structure type objects also known
as structure variable.
• In C programming, there are two ways to declare a structure variable:
1. Along with structure definition
2. After structure definition

1.Declaration along with the structure definition

2.Declaration after Structure definition

Access Structure member (data)

• Structure is a complex data type, we cannot assign any value directly to it

using assignment operator.
• We must assign data to individual structure members separately.

CODING GEEKZ (Dr.S.Priya)

 10

• C supports two operators to access structure members, using a structure

variable.
1. Dot/period operator (.)
2. Arrow operator (->)

1. Dot/period operator (.)

• It is known as member access operator. We use dot operator to access

members of simple structure variable.

Figure: Dot/period operator

2. Arrow operator (->)

• In C language it is illegal to access a structure member from a pointer to

structure variable using dot operator.

• We use arrow operator to access structure member from pointer to structure.

Example:
Write a program to read and display student information using structure.

CODING GEEKZ (Dr.S.Priya)

 11

Array of Structure

• It can be defined as the collection of multiple structure variables where each

variable contains information about different entities.

• The array of structures in C are used to store information about multiple entities
of different data types.

Figure: Array of structure

Example for Array of structure
Write a program to read and display N student information using array of structure.

Nested Structure

• When a structure contains another structure, it is called nested structure.

Syntax:

CODING GEEKZ (Dr.S.Priya)

 12

• For example, we have two structures named Address and Student. To make
Address nested to Student, we have to define Address structure before and
outside Student structure and create an object of Address structure inside Student
structure.
Example :

Write a program to read and display student information using nested of structure.

4. Self-referential structures

• Self-referential Structures are those structures that contain a reference to data of

its same type. i.e in addition to other data a self-referential structure contains a
pointer to a data that it of the same type as that of the structure. For example:
consider the structure node given as follows:

struct node
{
int val;
struct node *next;
};
• Here the structure node will contain two types of data an integer val and next
which is a pointer a node. Self-referential structure is the foundation of other
data structures.
• Such kinds of structures are used in different data structures such as to define
the nodes of linked lists, trees, etc.

CODING GEEKZ (Dr.S.Priya)

 13

Example 1:
Write a program to read and display student information using nested of
structure.

Example 2:

#include<stdio.h>
struct node {
int data;
struct node *link;
} n,b;
int main() {
n.data=3;
n.link=NULL;`
b.data=5;
b.link=NULL;
n.link=&b;
printf("%d",n.data);
printf("\n%d",n.link);
printf("\n%d",n.link->data);
}

5. Pointers and structures

• We can define a pointer that points to the structure like any other variable. Such
pointers are generally called Structure Pointers.
• We can access the members of the structure pointed by the structure pointer
using the ( -> ) arrow operator.
• Reference/address of structure object is passed as function argument to the
definition of function.

CODING GEEKZ (Dr.S.Priya)

 14

Example:

6. Dynamic memory allocation

• The process of reserving memory is called allocation. The way to allocate memory
depends on the type of memory.
• C has two types of memory: Static memory and dynamic memory.

Static Memory
• Static memory is memory that is reserved for variables before the program runs.
Allocation of static memory is also known as compile time memory allocation.
• C automatically allocates memory for every variable when the program is
compiled.
• For example, if you create an integer array of 20 students (e.g. for a summer
semester), C will reserve space for 20 elements which is typically 80 bytes of
memory (20 * 4).
• But when the semester starts, it turns out that only 12 students are attending.
Then you have wasted the space of 8 unused elements.

Dynamic Memory

• Dynamic memory is memory that is allocated after the program starts running.
Allocation of dynamic memory can also be referred to as runtime memory
allocation.
• Unlike with static memory, you have full control over how much memory is being
used at any time. You can write code to determine how much memory you need
and allocate it.
• Dynamic memory does not belong to a variable, it can only be accessed with
pointers.

To allocate memory dynamically, library functions are malloc(), calloc(), realloc()

and free() are used. These functions are defined in the <stdlib.h> header file.

CODING GEEKZ (Dr.S.Priya)

 15

malloc()

The name "malloc" stands for memory allocation. The malloc() function reserves
a block of memory of the specified number of bytes. And, it returns a pointer of
void which can be casted into pointers of any form.

Syntax of malloc()

ptr = (castType*) malloc(size);

Example

ptr = (float*) malloc(100 * sizeof(float));

• The above statement allocates 400 bytes of memory. It's because the size of
float is 4 bytes. And, the pointer ptr holds the address of the first byte in the
allocated memory.
• The expression results in a NULL pointer if the memory cannot be allocated.

Example 1: malloc() and free()

Program : To print n numbers

#include <stdio.h>
#include <stdlib.h> // Include for malloc and free

int main()
{
int n,i;
int *num;
printf("Enter the number of elements n:");
scanf("%d",&n);
num=(int*)malloc(n*sizeof(int));

if(num==NULL)
{
printf("Memory is full");
return 1;
}

for(i=0;i<n;i++)
{
printf("Enter the elements:");
scanf("%d",&num[i]);
printf("Address : %x\n",num+i);//print the address
}
printf("The entered values :");

CODING GEEKZ (Dr.S.Priya)

 16

for(i=0;i<n;i++)
{
printf("%d\n",num[i]);
}
return 1;
}

Output:

Enter the number of elements n:4

Enter the elements:1
Address : bc6b50
Enter the elements:2
Address : bc6b54
Enter the elements:3
Address : bc6b58
Enter the elements:4
Address : bc6b5c
The entered values :1
2
3
4

calloc()

The name "calloc" stands for contiguous allocation. The malloc() function allocates
memory and leaves the memory uninitialized, whereas the calloc() function
allocates memory and initializes all bits to zero.

Syntax of calloc()

ptr = (castType*)calloc(n, size);

Example:

ptr = (float*) calloc(25, sizeof(float));

The above statement allocates contiguous space in memory for 25 elements of

type float.

Example 2: calloc() and free()

CODING GEEKZ (Dr.S.Priya)

 17

Program : To print n numbers

#include <stdio.h>
#include <stdlib.h> // Include for malloc and free

int main()
{
int n,i;
int *num;
printf("Enter the number of elements n:");
scanf("%d",&n);
num=(int*)calloc(n,sizeof(int));

if(num==NULL)
{
printf("Memory is full");
return 1;
}

for(i=0;i<n;i++)
{
printf("Enter the elements:");
scanf("%d",&num[i]);
printf("Address : %x\n",num+i);//print the address
}
printf("The entered values :");
for(i=0;i<n;i++)
{
printf("%d\n",num[i]);
}
return 1;
}

OUTPUT:

Enter the number of elements n:4

Enter the elements:1
Address : b36b50
Enter the elements:2
Address : b36b54
Enter the elements:3
Address : b36b58
Enter the elements:4
Address : b36b5c
The entered values :1

CODING GEEKZ (Dr.S.Priya)

 18

2
3
4

free()

Dynamically allocated memory created with either calloc() or malloc() doesn't get
freed on their own. You must explicitly use free() to release the space.

Syntax of free()

free(ptr);

This statement frees the space allocated in the memory pointed by ptr.

realloc()

If the dynamically allocated memory is insufficient or more than required, you can
change the size of previously allocated memory using the realloc() function.

Syntax of realloc()

ptr = realloc(ptr, x);

Here, ptr is reallocated with a new size x.

Example 3: realloc()

Program: Program to print n numbers

#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i,n1;
int *num;
printf("Enter n:");
scanf("%d",&n);

num=(int*)calloc(n,sizeof(int));

if(num==NULL)
{
printf("Memory is full");
return 1;
}

CODING GEEKZ (Dr.S.Priya)

 19

for(i=0;i<n;i++)
{
//scanf("%d",&num[i]);
printf("Address :%x\n",num+i);
}

printf("Enter the new size:");

scanf("%d",&n1);
printf("Enter the new elements:");
for(i=0;i<n1;i++) //new size
{
scanf("%d",&num[i]);
}

for(i=0;i<n1;i++)
{
printf("Element = %d and Address is %x\n",num[i],num+i);

}
free(num);
return 0;
}

Output:

Enter n:5
Address :a26b50
Address :a26b54
Address :a26b58
Address :a26b5c
Address :a26b60
Enter the new size:6
Enter the new elements:
1
2
3
4
5
6
Element = 1 and Address is a26b50
Element = 2 and Address is a26b54
Element = 3 and Address is a26b58
Element = 4 and Address is a26b5c
Element = 5 and Address is a26b60
Element = 6 and Address is a26b64

CODING GEEKZ (Dr.S.Priya)

 20

7. Matrix multiplication

• A matrix is a grid that is used to store data in a structured format. It is often

used with a table, where the data is represented in horizontal rows and vertical
columns.
• Matrices are often used in programming languages and are used to represent
the data in a graphical structure.
• The definition of matrix multiplication indicates a row-by-column
multiplication, where the entry in the ith row and jth column of the product AB
is obtained by multiplying the entries in the ith row A of by the corresponding
entries in the jth column of B and then adding the results.

The general pattern for matrix multiplication is as follows.

Algorithm:

Step 1: Start the Program.

Step 2: Enter the row and column of the first (a) matrix.

Step 3: Enter the row and column of the second (b) matrix

Step 4: Enter the elements of the first (a) matrix.

Step 5: Enter the elements of the second (b) matrix.

Step 6: Print the elements of the first (a) matrix in matrix form.

Step 7: Print the elements of the second (b) matrix in matrix form.

Step 8: Set a loop up to row.

Step 9: Set an inner loop up to the column.

Step 10: Set another inner loop up to the column.

Step 11: Multiply the first (a) and second (b) matrix and store the element in the
third matrix (c)

Step 12: Print the final matrix.

Step 13: Stop the Program.

CODING GEEKZ (Dr.S.Priya)

 21

Example: Matrix Multiplication using Dynamic Memory allocation

#include <stdio.h>
#include <stdlib.h>

// Function to multiply two matrices

void multiplyMatrices(int** firstMatrix, int rows1, int cols1, int** secondMatrix,
int rows2, int cols2, int** resultMatrix) {
int i, j, k;
if (cols1 != rows2) {
printf("Matrix multiplication not possible: incompatible dimensions.\n");
return;
}

for (i = 0; i < rows1; i++) {

for (j = 0; j < cols2; j++) {
resultMatrix[i][j] = 0;
for (k = 0; k < cols1; k++) {
resultMatrix[i][j] += firstMatrix[i][k] * secondMatrix[k][j];
}
}
}
}

// Function to print a matrix

void printMatrix(int** matrix, int rows, int cols) {
int i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}

// Function to free allocated memory for a matrix

void freeMatrix(int** matrix, int rows) {
int i;
for (i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
}

CODING GEEKZ (Dr.S.Priya)

 22

int main() {
int rows1, cols1, rows2, cols2;
int i, j;

// Get dimensions for the first matrix from the user

printf("Enter the number of rows and columns for the first matrix: ");
scanf("%d %d", &rows1, &cols1);

// Allocate memory for the first matrix

int **firstMatrix = (int**)malloc(rows1 * sizeof(int*));
for (i = 0; i < rows1; i++) {
firstMatrix[i] = (int*)malloc(cols1 * sizeof(int));
}

// Get the first matrix elements from the user

printf("Enter elements of the first matrix:\n");
for (i = 0; i < rows1; i++) {
for (j = 0; j < cols1; j++) {
printf("Element [%d][%d]: ",i,j);
scanf("%d", &firstMatrix[i][j]);
}
}

// Get dimensions for the second matrix from the user

printf("Enter the number of rows and columns for the second matrix: ");
scanf("%d %d", &rows2, &cols2);

// Allocate memory for the second matrix

int** secondMatrix = (int**)malloc(rows2 * sizeof(int*));
for (i = 0; i < rows2; i++) {
secondMatrix[i] = (int*)malloc(cols2 * sizeof(int));
}

// Get the second matrix elements from the user

printf("Enter elements of the second matrix:\n");
for (i = 0; i < rows2; i++) {
for (j = 0; j < cols2; j++) {
printf("Element [%d][%d]: ", i, j);
scanf("%d", &secondMatrix[i][j]);
}
}

CODING GEEKZ (Dr.S.Priya)

 23

// Allocate memory for the result matrix

int **resultMatrix = (int**)malloc(rows1 * sizeof(int*));
for (i = 0; i < rows1; i++) {
resultMatrix[i] = (int*)malloc(cols2 * sizeof(int));
}

// Multiply the matrices

multiplyMatrices(firstMatrix, rows1, cols1, secondMatrix, rows2, cols2,
resultMatrix);

// Print the result

printf("Result of matrix multiplication:\n");
printMatrix(resultMatrix, rows1, cols2);

// Free allocated memory

freeMatrix(firstMatrix, rows1);
freeMatrix(secondMatrix, rows2);
freeMatrix(resultMatrix, rows1);

return 0;
}

Output:

Enter the number of rows and columns for the first matrix: 2
2
Enter elements of the first matrix:
Element [0][0]: 1
Element [0][1]: 1
Element [1][0]: 1
Element [1][1]: 1
Enter the number of rows and columns for the second matrix: 2
2
Enter elements of the second matrix:
Element [0][0]: 1
Element [0][1]: 1
Element [1][0]: 1
Element [1][1]: 1
Result of matrix multiplication:
22
22

CODING GEEKZ (Dr.S.Priya)

 24

Data Structure – Definition

• Data Structure can be defined as the group of data elements which provides an
efficient way of storing and organizing data in the computer so that it can be used
efficiently.
• Data structures make it easy for users to access and work with the data they need
in appropriate ways.

Data Structure – Types

• Data Structures are divided into primitive data structures and non-primitive
data structures.
• Basic types provided by a programming language as building blocks are called as
primitive data structures.
• Complex data structures that are built using primitive data types are called as
non-primitive data structures.

Figure: Classification of Data Structure

Based on the organizing method of data structure, non-primitive data structures are divided
into two types.

• Linear Data Structures

• Non - Linear Data Structures

Linear Data Structures

If a data structure organizes the data in sequential order, then that data structure is called a
Linear Data Structure.

Example : Arrays, List (Linked List), Stack, Queue

CODING GEEKZ (Dr.S.Priya)

 25

Non - Linear Data Structures

If a data structure organizes the data in random order, then that data structure is called as
Non-Linear Data Structure.

Example: Tree, Graph, Dictionaries, Heaps

, , , ,
Example: Tree Graph Dictionaries Heaps Tries, Etc.,

Data Structure – Operations

• The data in the data structures are processed by certain operations.
o Traversing - Visiting each record so that items in the records can be
accessed.
o Searching - Finding the location of the record with a given key or value or
finding all records which satisfy given conditions.
o Inserting - Adding a new record to the data structure.
o Updating – Change the content of some elements of the record.
o Deleting - Removing records from the data structure.
o Sorting - Arranging records in some logical or numerical order. (Eg:
Alphabetic order)
o Merging - Combing records from two different sorted files into a single file.

Example:

▪ An organization contains a membership file in which each record contains the

following data for a given member:

Name, Address, Telephone Number, Age, Sex

a. Suppose the organization wants to announce a meeting through a mailing.

Then one would traverse the file to obtain Name and Address of each
member.

b. Suppose one wants to find the names of all members living in a particular area.
Again traverse and search the file to obtain the data.

c. Suppose one wants to obtain Address of a specific Person. Then one would
search the file for the record containing Name.

d. Suppose a member dies. Then one would delete his or her record from the
file.

e. Suppose a new person joins the organization. Then one would insert a record
into the file

f. Suppose a member has shifted to a new residence his/her address and

telephone number need to be changed. Given the name of the member, one

CODING GEEKZ (Dr.S.Priya)

 26

would first need to search for the record in the file. Then perform the update
operation, i.e. change some items in the record with the new data.

g. Suppose one wants to find the number of members whose age is 65 or above.
Again one would traverse the file, counting such members.

Abstract Data type (ADT)

• An Abstract Data type (ADT) is a type for objects whose behavior is defined by a
set of value and a set of operations.

• ADT refers to a set of data values and associated operations that are specified
accurately, independent of any particular implementation.

ADT = Type + Function Names + Behaviour of each function

• The ADT consists of a set of definitions that allow us to use the functions while
hiding the implementation.

• Abstract in the context of data structures means everything except the detailed
specifications or implementation.

• Data type of a variable is the set of values that the variable can take. Examples:
Stacks, Queues, Linked List

• While modeling the problems the necessary details are separated out from the
unnecessary details. This process of modeling the problem is called abstraction.

• The model defines an abstract view to the problem. It focuses only on problem
related stuff and that you try to define properties of the problem.

• Abstract data type operations are

• Create - Create the data structure.

• Display - Displaying all the elements stored in the data structure.

• Insert - Elements can be inserted at any desired position.

• Delete - Desired element can be deleted from the data structure.

• Modify - Any desired element can be deleted/modified from the data

structure.

• The ADT model has two different parts functions (public and private) and data
structures. Both are contained within the ADT model itself, and do not come within
the scope of the application program.

CODING GEEKZ (Dr.S.Priya)

 27

Figure : Abstract Data Type

• Data are entered, accessed, modified and deleted through the external application
programming interface. For each ADT operation, there is an algorithm that
performs its specific task.

• The operation name and parameters are available to the application, and they
provide only an interface to the application.

• When a list is controlled entirely by the program, it is implemented using simple

structure.

Mathematical notations - Big O, Omega and Theta

• The order of growth of the running time of an algorithms, gives a simple
characterization of algorithms efficiency.

• It also allows to compare relative performance of alternative algorithms.

• Asymptotic order is concerned with how the running time of an algorithm

increases with the size of the input, if input increases from small value to large
values

1. Big-Oh notation (O)

2. Big-Omega notation (Ω)

3. Theta notation (θ)

4. Little-oh notation (o)

5. Little-omega notation (ω)

Big-Oh Notation (O)

• Big-oh notation is used to define the worst-case running time of an algorithm
and concerned with large values of n.

CODING GEEKZ (Dr.S.Priya)

 28

• Definition: A function t(n) is said to be in O(g(n)), denoted as t(n) ϵ O(g(n)), if t(n) is

bounded above by some constant multiple of g(n) for all large n. i.e., if there exist
some positive constant c and some non-negative integer n0 such that

t(n) ≤ cg(n) for all n ≥ n0

• O(g(n)): Class of functions t(n) that grow no faster than g(n).

• Big-oh puts asymptotic upper bound on a function.

Figure: Big-oh notation

1< log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn
upper bound
Big-Omega notation (Ω)
• This notation is used to describe the best case running time of algorithms and
concerned with large values of n.

• Definition: A function t(n) is said to be in Ω(g(n)), denoted as t(n) ϵ Ω(g(n)), if t(n) is

bounded below by some positive constant multiple of g(n) for all large n. i.e., there
exist some positive constant c and some non-negative integer n0. Such that

t(n) ≥cg(n) for all n ≥ n0

• It represents the lower bound of the resources required to solve a problem.

CODING GEEKZ (Dr.S.Priya)

 29

Figure: Big- Omega notation

1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn
lower bound
Theta notation (θ)
Definition: A function t(n) is said to be in θ(g(n)), denoted t(n) ϵ θ(g(n)), if t(n) is bounded
both above and below by some positive constant multiples of g(n) for all large n. i.e., if
there exist some positive constant c1 and c2 and some non-negative integer n0 such that

c2g(n) ≤ t(n) ≤ c1g(n) for all n > n0

θ(g(n)) = O(g(n)) ∩ Ω(g(n))

Figure: Big-Theta notation

1 < log n < √n < n < n logn < n2 < n3 < ……………< 2n < 3n < …. <nn
average bound

CODING GEEKZ (Dr.S.Priya)

 30

Figure: Asymptotic Notations

Little-oh notation (o)
▪ This notation is used to describe the worst case analysis of algorithms and
concerned with small values of n.
▪ Definition : A function t(n) is said to be in o(g(n)), denoted t(n) ϵ o(g(n)), if there
exist some positive constant c and some non-negative integer such that

t(n) ≤ cg(n)

Little-omega notation (ω)

▪ This notation is used to describe the best case analysis of algorithms and
concerned with small values of n.

▪ The function t(n) = ω(g(n)) iff

CODING GEEKZ (Dr.S.Priya)

 31

Complexity – Time, Space, Trade off.

▪ The best algorithm to solve a particular problem at hand is no doubt the one that
requires less memory space and takes less time to complete its execution. But
practically, designing such an ideal algorithm is not a trivial task.

▪ There can be more than one algorithm to solve a particular problem. One may
require less memory space, while the other may require less CPU time to execute.
Thus, it is not uncommon to sacrifice one thing for the other.

▪ Hence, there exists a time–space trade-off among algorithms. So, if space is a big
constraint, then one might choose a program that takes less space at the cost of
more CPU time.

▪ On the contrary, if time is a major constraint, then one might choose a program
that takes minimum time to execute at the cost of more space.

YOUTUBE CHANNEL

CODING GEEKZ (Dr.S.Priya)