Abstract Data Type

In computer science, an abstract data type (ADT) is a mathematical model for data types,
defined by its behavior (semantics) from the point of view of a user of the data, specifically
in terms of possible values, possible operations on data of this type, and the behavior of these
operations.

Some examples of ADT are Stack, Queue, List etc.

 Stack −
o isFull(), This is used to check whether stack is full or not
o isEmpry(), This is used to check whether stack is empty or not
o push(x), This is used to push x into the stack
o pop(), This is used to delete one element from top of the stack
o peek(), This is used to get the top most element of the stack
o size(), this function is used to get number of elements present into the stack
 Queue −
o isFull(), This is used to check whether queue is full or not
o isEmpry(), This is used to check whether queue is empty or not
o insert(x), This is used to add x into the queue at the rear end
o delete(), This is used to delete one element from the front end of the queue
o size(), this function is used to get number of elements present into the queue

 List −
o size(), this function is used to get number of elements present into the list
o insert(x), this function is used to insert one element into the list
 o remove(x), this function is used to remove given element from the list
o get(i), this function is used to get element at position i
o replace(x, y), this function is used to replace x with y value

Asymptotic Notations

Asymptotic Notations The main idea of asymptotic analysis is to have a measure of

efficiency of algorithms that doesn’t depend on machine specific constants, and doesn’t
require algorithms to be implemented and time taken by programs to be compared.
Asymptotic notations are mathematical tools to represent time complexity of algorithms for
asymptotic analysis. The following three asymptotic notations are mostly used to represent
time complexity of algorithms.
The Big O Notation:
The Big O notation defines an upper bound of an algorithm, it
bounds a function only from above. For example, consider the
case of Insertion Sort. It takes linear time in best case and
quadratic time in worst case. We can safely say that the time
complexity of Insertion sort is O(n2). Note that O(n2) also covers
linear time.

The Big O notation is useful when we only have upper bound on

time complexity of an algorithm. Many times we easily find an
upper bound by simply looking at the algorithm.

For a given function g(n), we denote by O(g(n)) the set of functions.

O(g(n)) = { f(n): there exist positive constants c and n0, such that 0 ≤
f(n)≤ c×g(n) for all n ≥ n0}
Example

f(n) = 2n + 3

2n + 3 ≤ 10 n ∀ n ≥ 1
Here, c=10, n0=1,
g(n)=n
=> f(n) = O(n)

3n 2n + 3 ≤ 5 n ∀ n ≥
Also, 2n + 3 ≤ 2 n +

And, 2n + 3 ≤ 2n2 +
3n2 2n + 3 ≤ 5n2
=> f(n) = O(n2)

O(1) < O(log n) < O(√ n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n) < O(3n) < O(nn)
 The Omega (Ω) notation:

Just as Big O notation provides an asymptotic upper

bound on a function, Ω notation provides an asymptotic
lower bound.

Ω notation can be useful when we have lower bound on

time complexity of an algorithm. As discussed in the
previously, the best case performance of an algorithm is
generally not useful, the omega notation is the least used
notation among all three.

For a given function g(n), we denote by Ω(g(n)) the set of

functions.

Ω (g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤

c×g(n) ≤ f(n) for all n ≥ n0 }.

Let us consider the same insertion sort example here. The time complexity of
insertion sort can be written as Ω(n), but it is not a very useful information
about insertion sort, as we are generally interested in worst case and sometimes
in average case.

Example :

f(n) = 2n + 3

2n + 3 ≥ n ∀ n ≥ 1
Here, c=1, n0=1,
g(n)=n
=> f(n) = Ω(n)
Also, f(n) = Ω(log n)
f(n) = Ω(√n)

The Theta (Θ) notation:

The theta notation bounds a functions from above and

below, so it defines the exact asymptotic behaviour. A
simple way to get theta notation of an expression is to
drop low order terms and ignore leading constants. For
example, consider the following expression.
3n3 + 6n2 + 6000 = Θ(n3)

Dropping lower order terms is always fine because there will always be a n0
after which Θ(n3) has higher values than Θ(n2) irrespective of the constants
involved. For a given function g(n), we denote Θ(g(n)) as the following set of
functions.

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0
≤ c1×g(n) ≤ f(n) ≤ c2×g(n) for all n ≥ n0}
 The above definition means, if f(n) is theta of g(n), then the value f(n)
is always between c1×g(n) and c2×g(n) for large values of n (n ≥ n0).
The definition of theta also requires that f(n) must be non-negative for
values of n greater than n0.

Example

f(n) = 2n + 3

1 * n ≤ 2n + 3 ≤
5n

∀ n ≥ 1 Here,
c1=1, c2 = 5,
n0=1, g(n)=n
=> f(n) = Θ(n)

Example 7.5:

f(n) = 2n2 + 3n + 4

2n2 + 3n + 4 ≤ 2n2 + 3n2 + 4n2

2n2 + 3n
+4≤
9n2 f(n)
= O (n2)

also, 2n2 + 3n
+ 4 ≥ 1 * n2 f(n)
= Ω (n2)

9n2 ∀ n ≥ 1 Here, c1=1, c2

=>1 * n2 ≤ 2n2 + 3n + 4 ≤

= 9, n0=1, g(n)= n2
=> f(n) = Θ(n2)

Example
f(n) = n2 log n + n

n2 log n ≤ n2 log n + n
≤ 10 n2 log n Ω (n2 log
 n) Θ(n2 log n) O(n2 log
n)

Example
f(n) = n!
=1×2×3×4×…×n
1×1×1×…×1≤1×2×3×4×…×n ≤
n × n × n × … × n 1 ≤ n! ≤ nn
Ω (1) O (nn) ( Here we cannot find the average or tight bound Θ)

Complexity Analysis of Data Structures and Algorithms

Complexity analysis is defined as a technique to measure how long an algorithm
would take to complete given an input of size n; independent of the machine,
language, and compiler. It is used for evaluating the variations of execution time
on different algorithms.
Why Complexity Analysis is Required?

 It gives you an estimated time and space required to execute a program.

 It is used for comparing different algorithms for different input sizes.
 It helps to determine the difficulty of a problem.

Asymptotic Notations for Determining Complexities

Your algorithm doesn't need to behave in the same way for different input sizes. Its
performance may vary. The study of the variations in the performance of the
algorithm with the change in the order of the input size is called Asymptotic
Analysis.
Asymptotic notations are mathematical notations to describe the running time of
an algorithm when the input tends towards a particular value or a limiting value. In
other words, it defines the mathematical limits of its run-time performance. Using
the asymptotic analysis, we can easily conclude the average-case, best-case, and
worst-case scenario of an algorithm.

There are mainly three asymptotic notations for the complexity analysis of
algorithms. They are as follows:

1. Big-O notation
2. Omega notation
3. Theta notation
 1. Big O notation (O-notation)
Big O notation symbolizes the upper bound of the running time of an algorithm or
the algorithm's longest amount of time to complete its operation. Therefore, it
gives the worst-case complexity of an algorithm.

Mathematical Representation of Big-O Notation

O(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
In the above expression, a function f(n) belongs to the set O(g(n)) if there exists a
positive constant c such that it lies between 0 and cg(n), for sufficiently large n.
For any value of n, the running time of an algorithm does not cross the time
provided by O(g(n)).
We will look at the Big O notation in much detail in the next section, Big O
Notation in Data Structures.

2. Omega notation (Ω-notation)

Omega notation symbolizes the lower bound of the running time of an algorithm.
Thus, it provides the best-case complexity of an algorithm. It determines the
fastest time that an algorithm can run.
Mathematical Representation of Omega Notation

Ω(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
In the above expression, a function f(n) belongs to the set Ω(g(n)) if there exists a
positive constant c such that it lies above cg(n), for sufficiently large n. For any
value of n, the minimum time required by the algorithm is given by Omega
Ω(g(n)).
3. Theta Notation (Θ-notation)
Theta notation symbolizes the upper and the lower bound of the running time of an
algorithm. In real-world problems, an algorithm does not perform worst or best, it
fluctuates between the worst-case and best-case, and this gives us the average case
complexity of an algorithm.
Mathematical Representation of Theta Notation

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0

such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }
In the above expression, a function f(n) belongs to the set Θ(g(n)) if there exist
positive constants c1 and c2 such that it can be sandwiched
between c1g(n) and c2g(n), for sufficiently large n. If a function f(n) lies anywhere
in between c1g(n) and c2g(n) for all n ≥ n0, then f(n) is said to be asymptotically
tight bound.

Parameters to Measure Complexities

1. Time Complexity
Time complexity is the amount of time taken by an algorithm to execute each
statement of the code till its completion. The time taken here is for the function of
the length of the input and not the actual execution time of the machine on which
the algorithm is running. The time complexity of algorithms is commonly
expressed using the Big O notation.
To calculate the time complexity, total the cost of each fundamental instruction
and the number of times the instruction is executed.

 There are statements with basic operations like comparisons, return

statements, assignments, and reading a variable. Let's assume that each
statement takes constant time O(1).

Example

int a=5; // reading a variable

if( a==5) return true; // return statement
int x= 4>5 ? 1:0; // comparison
bool flag=true; // Assignment
Total time taken, T(n) = t(statement1) + t(statement2) + ... + t(statementN);
T(n)=O(1) i.e. constant complexity

Here, n is the input size, and t represents the amount of time that a statement
or collection of statements takes to execute.

 To calculate the time taken by any loop, find out the runtime of the loop
block and multiply it by the number of times the program will repeat the
loop.

Example

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

cout << “ScholarHat” << endl;
 }

In the above code, the loop will execute n times, and it will
print ScholarHat N times.

Total time taken, T(N) = n *( t(cout statement))

= n * O(1)
= O(n) i.e. Linear complexity.

2. Space Complexity
Space complexity is the amount of memory space an algorithm or a problem takes
during the execution of that particular problem/algorithm. Here, the space used
includes both, the variables and the input values. Space complexity is the
combination or sum up of the auxiliary space and the space used by input values.
Auxiliary space is the temporary space required by an algorithm/problem during
the execution of that algorithm/problem.
Space Complexity = Auxiliary Space + Space used for input values. It is
frequently represented using Big O notation, just like time complexity, to describe
the maximum amount of memory utilization. To get the space complexity, one
must know the amount of memory used by different types of datatype variables,
program instructions, constant values, and things like function calls, recursion
stacks, etc.
Let's calculate the space complexity for the code of Addition of Numbers

Example

{
int sum = x + y;
return sum;
}
In the above code, we have 3 integer variables sum, x, and y. All the variables will
take 4 bytes of space, and an extra 4-byte for the return value sum. Hence, the total
space complexity = 4*4 + 4 = 20 bytes. This is the fixed complexity and because
of the same type of inputs, such space complexities are considered as constant
space complexities or so-called O(1) space complexity.

How to optimize an Algorithm?

We can optimize a solution using both time and space optimization. To
optimize a program,
  Reduce the time taken to run the program and increase the
space occupied.
 Reduce the memory usage of the program and increase its total
run time.
 Reduce both time and space complexity by deploying relevant
algorithms.

Common Asymptotic Notations

Type of Complexity Asymptotic Notation

constant ?(1)

linear ?(n)

logarithmic ?(log n)

n log n ?(n log n)

exponential 2?(n)

cubic ?(n3)

polynomial n?(1)

quadratic ?(n2)

Complexity Analysis Of Algorithms

Algorithm Complexity
Linear Search Algorithm O(N)

Binary Search O(LogN)

Bubble Sort O(N^2)

Insertion Sort O(N^2)

Selection Sort O(N^2)

QuickSort O(N^2)

Merge Sort O(N log(N))

Radix Sort O((n+b) * logb(k)).

Breadth First Search O(V+E)

Depth First Search O(V+E)

Worst-case time complexity of

different data structures for
different operations
Data structure Access Search Insertion Deletion
Array O(1) O(N) O(N) O(N)

Stack O(N) O(N) O(1) O(1)

Queue O(N) O(N) O(1) O(1)

Singly Linked List O(N) O(N) O(N) O(N)

Doubly Linked List O(N) O(N) O(1) O(1)

Hash Table O(N) O(N) O(N) O(N)

Binary Search Tree O(N) O(N) O(N) O(N)

AVL Tree O(log N) O(log N) O(log N) O(log N)

Binary Tree O(N) O(N) O(N) O(N)

Red Black Tree O(log N) O(log N) O(log N) O(log N)

Linked Lists:
A Linked list is an ordered collection of elements. Each element
in the list is referred as a node. Each node contains two fields
namely,
Data field-The data field contains the actual data of the
elements to be stored in the list Next field- The next field
contains the address of the next node in the list

DATA NEXT
 A Linked list node

Null 10 40 20 30

L
Advantages of Linked list:
1. Insertion and deletion of elements can be done efficiently
2.It uses dynamic memory allocation
3.Memory utilization is efficient compared to arrays
Disadvantages of linked list:
1. Linked list does not support random access
2.Memory is required to store next field
3.Searching takes time compared to arrays
Types of Linked
List
1. Singly Linked List or One Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List
Dynamic allocation

The process of allocating memory to the variables during

execution of the program or at run time is known as dynamic
memory allocation. C language has four library routines which
allow this function.
Dynamic memory allocation gives best performance in
situations in which we do not know memory requirements in
advance. C provides four library routines to automatically
allocate memory at the run time.
To use dynamic memory allocation functions, you must include the
header file stdlib.h.
malloc()
The malloc function reserves a block of memory of
specified size and returns a pointer of type void. This
means that we can assign it to any type of pointer.
The general syntax of malloc()
is ptr =(cast-
type*)malloc(
byte- size);
where ptr is a pointer of type cast-type. malloc() returns a
pointer (of cast type) to an area of memory with size
byte-size.
calloc():
calloc() function is another function that reserves memory at
the run time. It is normally used to request multiple blocks of
storage each of the same size and then sets all bytes to zero.
calloc() stands for contiguous memory allocation and is
primarily used to allocate memory for arrays. The syntax of
calloc() can be given as:
ptr=(cast-type*) calloc(n,elem-size);
The above statement allocates contiguous space for n
blocks each of size elem-size bytes. The only difference
between malloc() and calloc() is that when we use
calloc(), all bytes are initialized to zero. calloc() returns a
pointer to the first byte of the allocated region. free():
The free() is used to release the block of memory.
Syntax:
The general
syntax of the
free()function is,
free(ptr);
where ptr is a pointer that has been created by using
 malloc() or calloc(). When memory is deallocated using free(),
it is returned back to the free list within the heap.
realloc():
At times the memory allocated by using calloc() or
malloc() might be insufficient or in excess. In both the
situations we can always use realloc() to change the
memory size already allocated by calloc() and malloc().
This process is called reallocation of memory. The
general syntax for realloc() can be given as,
ptr = realloc(ptr,newsize);
variable ptr. It returns a pointer to the first byte of the memory
block. The allocated new block may be or may not be at the
same region. Thus, we see that realloc() takes two arguments.
The first is the pointer referencing the memory and the second is
the total number of bytes you want to reallocate.

Differences between Array based and Linked based

implementation

Array Linked List

Linked list is an ordered

Array is a collection of elements
collection of elements
Definition having same data type with
which are connected by
common name
links/pointers

Elements can be accessed

Access Sequential access
using index/subscript, random
access

Elements are stored in contiguous Elements are stored at

Memory structure
memory locations available memory space

Insertion and deletion takes more time Insertion and deletion are fast
Insertion & Deletion
in array and easy
 Memory is allocated at run
Memory is allocated at compile time
Memory Allocation time i.e dynamic memory
i.e static memory allocation
allocation

Types 1D,2D,multi-dimensional SLL, DLL circular linked list

Each node is dependent

on each other as address
Dependency Each elements is independent
part contains address of
next node in the list

SINGLY LINKED LIST

A singly linked list is a linked list in which each node
contains only one link field pointing to the next node in
the list

SLL

SLL with a Header

Basic operations on a singly-linked list are:
1. Insert – Inserts a new node in the list.
2. Delete – Deletes any node from the list.
3. Find – Finds the position( address ) of any node in the
list.
 4. FindPrevious - Finds the position( address ) of the
previous node in the list.
5. FindNext- Finds the position( address ) of the next
node in the list.
6. Display-display the date in the list
7. Search-find whether a element is present in the list or
not

SINGLY LINKED LIST OR ONE WAY CHAIN

Singly linked list can be defined as the collection of ordered
set of elements. The number of elements may vary according
to need of the program. A node in the singly linked list consist
of two parts: data part and link part. Data part of the node
stores actual information that is to be represented by the
node while the link part of the node stores the address of its
immediate successor.

One way chain or singly linked list can be traversed only in

one direction. In other words, we can say that each node
contains only next pointer, therefore we can not traverse the
list in the reverse direction.

Consider an example where the marks obtained by the

student in three subjects are stored in a linked list as shown
in the figure.

In the above figure, the arrow represents the links. The

data part of every node contains the marks obtained by the
student in the different subject. The last node in the list is
identified by the null pointer which is present in the address
part of the last node. We can have as many elements we
require, in the data part of the list.
 Operations on Singly Linked List
There are various operations which can be performed on
singly linked list. A list of all such operations is given below.

Node Creation
1
.

s
t
r
u
c
t

n
o
d
e

2
.

{
3. int data;
4.
6. struct node *head, *ptr;
7. ptr = (struct node *)malloc(sizeof(struct node *));
Insertion
The insertion into a singly linked list can be performed at
different positions. Based on the position of the new node
being inserted, the insertion is categorized into the following
categories.
SN Operation Description

1 Insertion at It involves inserting any element at the front of the list. We just
beginning need to a few link adjustments to make the new node as the
head of the list.

2 Insertion at end of It involves insertion at the last of the linked list. The new node
the list can be inserted as the only node in the list or it can be inserted
as the last one. Different logics are implemented in each
scenario.

3 Insertion after It involves insertion after the specified node of the linked list.
specified node We need to skip the desired number of nodes in order to reach
the node after which the new node will be inserted. .

Deletion and Traversing

The Deletion of a node from a singly linked list can be
performed at different positions. Based on the position of the
node being deleted, the operation is categorized into the
following categories.

SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list. This
beginning is the simplest operation among all. It just need a few adjustments
in the node pointers.

2 Deletion at the It involves deleting the last node of the list. The list can either be
end of the list empty or full. Different logic is implemented for the different

scenarios.
3 Deletion after It involves deleting the node after the specified node in the list. we need to
specified node skip the desired number of nodes to reach the node after which the node
will be deleted. This requires traversing through the list.

4 Traversing In traversing, we simply visit each node of the list at least once in order to
perform some specific operation on it, for example, printing data part of
each node present in the list.

5 Searching In searching, we match each element of the list with the given element. If
the element is found on any of the location then location of that element is
returned otherwise null is returned. .

Advantages of SLL
1. The elements can be accessed using the next link
2. Occupies less memory than DLL as it has only one next field.
Disadvantages of SLL
1. Traversal in the backwards is not possible
2. Less efficient to for insertion and deletion.

DOUBLY-LINKED LIST
A doubly linked list is a linked list in which each node
has three fields namely Data, Next, Prev. Data-This
field stores the value of the element
Next-This field points to the successor node in the list Prev-This field
points to the predecessor node in the list

PREV DATA NEXT

DLL NODE
DOUBLY LINKED LIST

Basic operations of a doubly -linked list are:

1. Insert – Inserts a new element at the end of the list.
2. Delete – Deletes any node from the list.
3. Find – Finds any node in the list.
4. Print – Prints the list

Doubly linked list is a complex type of linked list in which a

node contains a pointer to the previous as well as the next
node in the sequence. Therefore, in a doubly linked list, a
node consists of three parts: node data, pointer to the next
node in sequence (next pointer) , pointer to the previous node
(previous pointer). A sample node in a doubly linked list is
shown in the figure.

A doubly linked list containing three nodes having numbers

from 1 to 3 in their data part, is shown in the following image.
 In C, structure of a node in doubly linked list can be given as :

1
.

s
t
r
u
c
t

n
o
d
e

2
.

{
3. struct node *prev;
4. int data;
5.
The prev part of the first node and the next part of the last
node will always contain null indicating end in each direction.

In a singly linked list, we could traverse only in one direction,

because each node contains address of the next node and it
doesn't have any record of its previous nodes. However,
doubly linked list overcome this limitation of singly linked list.
Due to the fact that, each node of the list contains the
address of its previous node, we can find all the details about
the previous node as well by using the previous address
stored inside the previous part of each node.
Memory Representation of a doubly linked list
Memory Representation of a doubly linked list is shown in the
following image. Generally, doubly linked list consumes more
space for every node and therefore, causes more expansive
basic operations such as insertion and deletion. However, we
can easily manipulate the elements of the list since the list
maintains pointers in both the directions (forward and
backward).

In the following image, the first element of the list that is i.e.
13 stored at address 1. The head pointer points to the starting
address 1. Since this is the first element being added to the
list therefore the prev of the list contains null. The next
node of the list resides at address 4 therefore the first node
contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing
null or -1 in its next part.
 Operations
on doubly
linked list
Node
Creation

1
.

s
t
r
u
c
t

n
o
d
e

2
.

{
3. struct node *prev;
4. int data;
5.
7. struct node *head;
All the remaining operations regarding doubly linked list are
described in the following table.

SN Operation Description
1 Insertion at beginning Adding the node into the linked list at beginning.