May 31
Explore Data Structure and Algorithm Part-3
Link Part 2:
https://m-alinkon10.medium.com/explore-data-structure-and-algorithm-part-2-6be67e89bcfe
Previous Part We discuss about linked list and Previous existing topic also disccus here
B2.3:Trees
B2.4: Trees have more diversion
B2.4.1: Stack.
B2.4.2: Queue
and finally
B2.4.3: Graph
Trees Data Structure :
A tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices.
Popular Tree-based Data Structure
**Binary Tree
**Binary Search Tree
**AVL Tree
**B-Tree
**B+ Tree
**Red-Black Tree
Stack Data Structure
In the stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be removed first.
It works just like a pile of plates where the last plate kept on the pile will be removed first
Queue Data Structure
Unlike stack, the queue data structure works in the FIFO principle where first element stored in the queue will be removed first.
It works just like a queue of people in the ticket counter where first person on the queue will get the ticket first
Graph Data Structure
In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges.
Popular Graph-Based Data Structures:
Spanning Tree and Minimum Spanning Tree
Strongly Connected Components
Adjacency Matrix
Adjacency List
Asymptotic Analysis: Big-O Notation and More
you will learn about Big-O notation, Theta notation and Omega notation.The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.
Asymptotic Notations
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic) to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time. These durations are denoted using asymptotic notations.
There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst-case complexity of an algorithm.
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.
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.
