Algorithm Time Complexity

Set DataStructure Time Complexity

DS	Container Build(A)	Static find(k)	Dynamic insert(x),delete(x)	Order find_min(),find_max()	Order find_next(),find_prev()
Unordered Array	n	n	n	n	n
Sorted Array	?	logn	n	1	logn

Permutation Sort Time Complexity
DS | Container Build(A) | Static find(k) | Dynamic insert(x),delete(x) | Order find_min(),find_max() | Order find_next(),find_prev() ——————-|—————–|————————–|—————————|—————————|——————– Unordered Array | n | n | n | n | n Sorted Array | n!xn | logn | n | 1 | logn

Selection Sort Time Complexity
DS | Container Build(A) | Static find(k) | Dynamic insert(x),delete(x) | Order find_min(),find_max() | Order find_next(),find_prev() ——————-|—————–|————————–|—————————|—————————|——————– Unordered Array | n | n | n | n | n Sorted Array | n^{2 | logn | n | 1 | logn}

Description
Sorting techniques
Permutation Sort:
Creates a permutation by randomly shuffling the elements. If the list is sorted,algorithm terminates.
If not, create a new permutation, repeating the process above.

Selection Sort:
Repeatedly finding the minimum element of the sort and moving it to the front.

Insertion Sort:
Sorts the unsorted data by inserting the unsorted data in the sorted part of the dataset.

Merge Sort:

Sorting
Destructive Sorting:
Overwrites an input array
Creating a new sorted list from an unsorted list without modifying the original list
-Original list is left untouched and a new sorted list is created
-Disadvantage: Requires additional memory to store the new sorted list, which may be a disadvantage if the original list is very large
In place Sorting: Sorting the original list in memory without creating a new list
Uses O(1) extra space
-Modifies the original list, rearranging its elements into sorted order.
-Advantage: Can be more efficient in terms of memory usage, as it doesn’t require additional memory to store a new sorted list
-Disadvantage: Can be more complex and require more careful implementation to ensure that it works correctly and efficiently.