Data Structures and Algorithms

A set is a data structure that stores a collection of unique elements. It does not maintain any specific order for the elements.

Binary search repeatedly divides the search interval in half until the element is found or the interval becomes empty. This results in a time complexity of O(log n).

Merge sort follows a divide-and-conquer approach, where the array is recursively divided into smaller subarrays, sorted, and then merged back together to obtain the sorted array.

Insertion sort has a worst-case time complexity of O(n^2) because it compares each element with all the elements to its left before inserting it in the correct position.

A queue is a data structure that follows the first-in-first-out (FIFO) principle, where elements are added at the rear and removed from the front.

In a binary heap, the minimum element is always stored at the root node. Therefore, finding the minimum element has a time complexity of O(1).

A graph is a data structure that consists of a set of nodes and a set of edges connecting these nodes. Each node has a unique identifier.

The time complexity of DFS on a graph is O(V + E) because it visits each vertex and edge once.

Quick sort is an in-place sorting algorithm that partitions the array into smaller subarrays and recursively sorts them.

In linear probing, the time complexity of finding an element in a hash table is O(n) in the worst case, as it may have to search through the entire table.

A stack is a data structure that follows the last-in-first-out (LIFO) principle, where elements are added and removed from the same end.

The time complexity of BFS on a graph is O(V + E) because it visits each vertex and edge once.

Merge sort is a stable sorting algorithm, meaning that the relative order of equal elements in the input is preserved in the sorted output.

In a balanced binary search tree, the time complexity of finding an element is O(log n) because the tree is height-balanced.

A priority queue is a data structure that stores elements with associated priorities. Elements with higher priorities are served before elements with lower priorities.