More than a Pathshala
What are the applications where tree data structure can be used?
Some of the real world applications where tree data structure is used is listed below:
XML/Markup
parsers use trees. For example Apache Xerces
, Xalan XSLT parser
.PDF
is a tree-based format.Heuristic
search uses tree-based structure for storing training related data. Cor example: Chess Game
File System
uses tree structure to store files and directories.When you should use binary search algorithm?
You should use binary search algorithm when the given list/array is in sorted
order.
What is the difference between Singly Linked List and Doubly Linked List?
Singly Linked List: Singly Linked list is one of the easiest implementation of Linked list which comprises of sequence of nodes and each node comprises of data and address to another node as shown below
Singly linked list allows you to traverse through one way. One of the major advantages of singly linked list over doubly linked list is that it uses less memory.
Doubly Lined List: In Doubly linked list, a node has three fields i.e data element, reference to previous node and reference to next node, which provides it capability to traverse in the forward direction as well as backward direction.
What is the worst case time complexity of Bubble sort algorithm?
The worst case occurs when the given list of elements is sorted but in descending order.
In this case, time complexity of bubble sort will be, Big Oh = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)
To Read about bubble sort in detail Click Here
What is the best case time complexity of Bubble sort Algorithm?
The best case occurs when the given list of elements is already sorted in ascending order and sorting was intended for ascending order or vice-versa.
In this case, there will be no swapping and iteration will be done for only once for n elements. Hence the best case time complexity of bubble sort will be O(n)
To Read about bubble sort in detail Click Here
What is the best case, average case and worst case time complexity of Heap sort?
The best case, average case and worst case time complexity of Heap sort is listed below:
Best Case | Average Case | Worst Case | |
Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) |
What is the best case, average case and worst case time complexity of Merge sort?
The best case, average case and worst case time complexity of Merge sort is listed below:
Best Case | Average Case | Worst Case | |
Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) |
What is the worst case time complexity of Quick sort?
In quick sort, we pick an element called the pivot in each step and re-arrange the array in such a way that all elements less than the pivot now appear to the left of the pivot, and all elements larger than the pivot appear on the right side of the pivot. In all subsequent iterations of the sorting algorithm, the position of this pivot will remain unchanged, because it has been put in its correct place.
The worst case of quicksort, which happens when the pivot we picked turns out to be the least element of the array to be sorted, in every step (i.e. in every recursive call). A similar situation will also occur if the pivot happens to be the largest element of the array to be sorted. In such case the time complexity of quick sort will be O(n^{2})
What is the best case, average case and worst case time complexity of Quick sort?
The best case, average case and worst case time complexity of Quick sort is listed below:
Best Case | Average Case | Worst Case | |
Quick Sort | O(nlogn) | O(nlogn) | O(n^{2}) |
What is the best case, average case and worst case time complexity of Selection sort?
The best case, average case and worst case time complexity of Selection sort is listed below:
Best Case | Average Case | Worst Case | |
Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) |
To read about Selection Sort Algorithm in detail Click Here