Algorithmic Notation: Format Conventions, Statement and Control Structures.

Time and Space Analysis: Data types and

Abstract data types, Types of Data structures; Primitive, Non primitive, Linear and Nonlinear Data structures.

➢ Asymptotic Notations:
• Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by understanding
how their efficiency changes as the input size grows.
• These notations provide a concise way to express the behavior of an algorithm’s time or space complexity as the
input size approaches infinity.
• Rather than comparing algorithms directly, asymptotic analysis focuses on understanding the relative growth
rates of algorithms’ complexities.

➢ Types:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)

1.Theta Notation(Θ-notation):

• Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of
the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.
• Theta (Average Case) You add the running times for each possible input combination and take the average in the
average case.

2.Big-O Notation (O-notation):

• Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-
case complexity of an algorithm.
• It is the most widely used notation for Asymptotic analysis.
• It specifies the upper bound of a function.
• The maximum time required by an algorithm or the worst-case time complexity.
• It returns the highest possible output value(big-O) for a given input.
• Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution in the
longest amount of time possible.
3. Omega Notation (Ω-notation):
• Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case
complexity of an algorithm.
• The execution time serves as a lower bound on the algorithm’s time complexity.
• It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of
time.

➢ Time Complexity:
• The time complexity of an algorithm quantifies the amount of time taken by an algorithm to
run as a function of the length of the input. Note that the time to run is a function of the
length of the input and not the actual execution time of the machine on which the algorithm
is running on.
• The valid algorithm takes a finite amount of time for execution. The time required by the
algorithm to solve given problem is called time complexity of the algorithm. Time complexity
is very useful measure in algorithm analysis.
• It is the time needed for the completion of an algorithm. To estimate the time complexity,
we need to consider the cost of each fundamental instruction and the number of times the
instruction is executed.

➢ Space Complexity:
• Problem-solving using computer requires memory to hold temporary data or final result
while the program is in execution. The amount of memory required by the algorithm to solve
given problem is called space complexity of the algorithm.
• The space complexity of an algorithm quantifies the amount of space taken by an algorithm
to run as a function of the length of the input. It is the amount of memory needed for the
completion of an algorithm.
• To estimate the memory requirement we need to focus on two parts:
1. A fixed part: It is independent of the input size. It includes memory for instructions (code),
constants, variables, etc.
2. A variable part: It is dependent on the input size. It includes memory for recursion stack, referenced
variables, etc.
➢ Abstract Data Types
• An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and behaviors for a data
structure, without specifying how these operations are implemented or how data is organized in memory.
 • The definition of ADT only mentions what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what algorithms will be used for
implementing the operations. It is called “abstract” because it provides an implementation-independent view.

Aspect Abstract Data Types (ADTs) User-Defined Data Types (UDTs)

Definition Defines a class of objects and the A custom data type created by
operations that can be performed combining or extending existing
on them, along with their primitive types, specifying both
expected behavior (semantics), structure and operations.
but without specifying
implementation details.
Focus What operations are allowed and How data is organized in memory
how they behave, without and how operations are executed.
dictating how they are
implemented.
Purpose Provides an abstract model to Allows programmers to create
define data structures in a concrete implementations of data
conceptual way. structures using primitive types.

Implementation Does not specify how operations Specifies how to create and organize
Details are implemented or how data is data types to implement the
structured. structure.

Usage Used to design and conceptualize Used to implement data structures

data structures. that realize the abstract concepts
defined by ADTs.

Example List ADT, Stack ADT, Queue ADT. Structures, classes, enumerations,
records.

➢ Example of ADT:
1.List ADT: The List ADT (Abstract Data Type) is a sequential collection of elements that
supports a set of operations without specifying the internal implementation. It provides an
ordered way to store, access, and modify data.
2.Stack ADT: The Stack ADT is a linear data structure that follows the LIFO (Last In, First
Out) principle. It allows elements to be added and removed only from one end, called the
top of the stack.

3.Queue ADT: The Queue ADT is a linear data structure that follows the FIFO (First In, First
Out) principle. It allows elements to be inserted at one end (rear) and removed from the
other end (front).

Aspect Primitive Data Structures Non-Primitive Data Structures

Definition Basic types provided by a Complex data structures that are
programming language as built using primitive data types.
building blocks.
Examples int, float, char, double, boolean, Arrays, lists, stacks, queues, trees,
byte, short, long. graphs, sets, maps, classes
Memory Allocated on the stack. Typically allocated on the heap.
Allocation
Size Fixed and predefined by the Dynamic and can vary during
language. runtime.
Storage Store single values. It can store multiple and complex
sets of data.
Operations Limited to basic arithmetic and Support a wide range of operations
logical operations. specific to the data structure.
Default Have default values (like 0 for int, Usually, initialize to null or require
Values false for boolean). explicit initialization.
Efficiency Generally more efficient in terms It can be less efficient due to
of memory and performance. additional memory and overhead.
Direct It can be accessed directly It may require special methods or
Access through their variable name. operations to access or manipulate.
Usage Used for representing simple Used for organising and managing
values and performing basic data in more complex ways.
operations.
➢ Difference between Linear and Non-linear Data Structures:

S.NO Linear Data Structure Non-linear Data Structure

1. In a linear data structure, data In a non-linear data structure, data
elements are arranged in a linear elements are attached in
order where each and every hierarchically manner.
element is attached to its previous
and next adjacent.
2. In linear data structure, single level Whereas in non-linear data
is involved. structure, multiple levels are
involved.
3. Its implementation is easy in While its implementation is
comparison to non-linear data complex in comparison to linear
structure. data structure.
4. In linear data structure, data While in non-linear data structure,
elements can be traversed in a data elements can’t be traversed in
single run only. a single run only.
5. In a linear data structure, memory is While in a non-linear data
not utilized in an efficient way. structure, memory is utilized in an
efficient way.

6. Its examples are: array, stack, While its examples are: trees and
queue, linked list, etc. graphs.
7. Applications of linear data Applications of non-linear data
structures are mainly in application structures are in Artificial
software development. Intelligence and image processing.
 8. Linear data structures are useful for Non-linear data structures are
simple data storage and useful for representing complex
manipulation. relationships and data hierarchies,
such as in social networks, file
systems, or computer networks.
9. Performance is usually good for Performance can vary depending on
simple operations like adding or the structure and the operation, but
removing at the ends, but slower for can be optimized for specific
operations like searching or operations.
removing elements in the middle.

➢ Stack: Stack is a linear data structure that follows LIFO (Last In First Out) Principle, the last
element inserted is the first to be popped out. It means both insertion and deletion
operations happen at one end only.
Basic Operations on Stack:
In order to make manipulations in a stack, there are certain operations provided to us.
• push() to insert an element into the stack
• pop() to remove an element from the stack
• top() Returns the top element of the stack.
• isEmpty() returns true if stack is empty else false.
• isFull() returns true if the stack is full else false.

➢ Queue: Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the
first element inserted is the first to be popped out.
Basic Terminologies of Queue
• Front: Position of the entry in a queue ready to be served, that is, the first entry that will
be removed from the queue, is called the front of the queue. It is also referred as
the head of the queue.
• Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.
• Size: Size refers to the current number of elements in the queue.
• Capacity: Capacity refers to the maximum number of elements the queue can hold.
Operations on Queue
1. Enqueue:Enqueue operation adds (or stores) an element to the end of the queue.
Steps:
1. Check if the queue is full. If so, return an overflow error and exit.
2. If the queue is not full, increment the rear pointer to the next available position.
3. Insert the element at the rear.

2 Dequeue: Dequeue operation removes the element at the front of the queue. The
following steps are taken to perform the dequeue operation:
 1. Check if the queue is empty. If so, return an underflow error.
2. Remove the element at the front.
3. Increment the front pointer to the next element.

3. Peek or Front Operation: This operation returns the element at the front end without
removing it.

Types of Queues
1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only
insert the element at the back and remove the element from the front of the
queue.
2. Double-Ended Queue (Deque): In a double-ended queue the insertion and
deletion operations, both can be performed from both ends. They are of two
types:
• Input Restricted Queue: This is a simple queue. In this type of queue,
the input can be taken from only one end but deletion can be done
from any of the ends.
• Output Restricted Queue: This is also a simple queue. In this type of
queue, the input can be taken from both ends but deletion can be
done from only one end.
3. Circular Queue: This is a special type of queue where the last position is
connected back to the first position. Here also the operations are performed in
FIFO order.
4. Priority Queue: A priority queue is a special queue where the elements are
accessed based on the priority assigned to them. They are of two types:
• Ascending Priority Queue: In Ascending Priority Queue, the elements
are arranged in increasing order of their priority values. Element with
smallest priority value is popped first.
• Descending Priority Queue: In Descending Priority Queue, the
elements are arranged in decreasing order of their priority values.
Element with largest priority is popped first.

➢ LINEAR SEARCH
Assume that item is in an array in random order and we have to find an item.
Then the only way to search for a target item is, to begin with, the first position
and compare it to the target. If the item is at the same, we will return the position
of the current item. Otherwise, we will move to the next position. If we arrive at
the last position of an array and still can not find the target, we return -1. This is
called the Linear search or Sequential search.
#include <iostream>
using namespace std;
 int search(int array[], int n, int x)
{
for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
Example:
#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) // If element is found
return i;
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;
int result = linearSearch(arr, n, key);
if (result != -1)
cout << "Element found at index: " << result << endl;
else
cout << "Element not found" << endl;
return 0;
}
➢ BINARY SEARCH
In a binary search, however, cut down your search to half as soon as you find the middle of
a sorted list. The middle element is looked at to check if it is greater than or less than the
value to be searched. Accordingly, a search is done to either half of the given list
#include <iostream>
using namespace std;

int binarySearch(int array[], int x, int low, int high)

{
while (low <= high) {
int mid = low + (high - low) / 2;

if (array[mid] == x)
return mid;
 if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}
Example:
#include <iostream>
using namespace std;
int binarySearch (int arr[], int n, int key) {
int low = 0, high = n - 1;

while (low <= high) {

int mid = (low + high) / 2; // Find the middle index

if (arr[mid] == key)
return mid; // Element found

if (arr[mid] < key)

low = mid + 1; // Search in right half
else
high = mid - 1; // Search in left half
}

return -1; // Element not found

int main() {
int arr[] = {10, 20, 30, 40, 50}; // Sorted array
int n = sizeof(arr) / sizeof(arr[0]);
int key = 30;

int result = binarySearch(arr, n, key);

if (result != -1)
cout << "Element found at index: " << result << endl;
else
cout << "Element not found" << endl;
 return 0;
}
Linear Search Binary Search
In linear search input data need not to In binary search input data need to be in
be in sorted. sorted order.
It is also called sequential search. It is also called half-interval search.
The time complexity of linear The time complexity of binary
search O(n). search O(log n).
Multidimensional array can be used. Only single dimensional array is used.
Linear search performs equality Binary search performs ordering
comparisons comparisons
It is less complex. It is more complex.
It is very slow process. It is very fast process.