# 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

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