@@ -215,28 +215,28 @@ Below is the list of some of the most used Big O notations and their performance
215215
216216###Data Structure Operations Complexity
217217
218- | Data Structure| Access| Search| Insertion| Deletion| Comments|
219- | -----------------------| :--------- :| :--------- :| :--------- :| :-- -------:| :--------|
220- | ** Array** | ` 1 ` | ` n ` | ` n ` | ` n ` | |
221- | ** Stack** | ` n ` | ` n ` | ` 1 ` | ` 1 ` | |
222- | ** Queue** | ` n ` | ` n ` | ` 1 ` | ` 1 ` | |
223- | ** Linked List** | ` n ` | ` n ` | ` 1 ` | ` 1 ` | |
224- | ** Hash Table** | -| ` n ` | ` n ` | ` n ` | In case of perfect hash function costs would be` O(1) ` |
225- | ** Binary Search Tree** | ` n ` | ` n ` | ` n ` | ` n ` | In case of balanced tree costs would be` O(log(n)) ` |
226- | ** B-Tree** | ` log(n) ` | ` log(n) ` | ` log(n) ` | ` log(n) ` | |
227- | ** Red-Black Tree** | ` log(n) ` | ` log(n) ` | ` log(n) ` | ` log(n) ` | |
228- | ** AVL Tree** | ` log(n) ` | ` log(n) ` | ` log(n) ` | ` log(n) ` | |
218+ | Data Structure| Access| Search| Insertion| Deletion| Comments|
219+ | -----------------------| :-------:| :-------:| :-------:| :-------:| :--------|
220+ | ** Array** | 1 | n | n | n | |
221+ | ** Stack** | n | n | 1 | 1 | |
222+ | ** Queue** | n | n | 1 | 1 | |
223+ | ** Linked List** | n | n | 1 | 1 | |
224+ | ** Hash Table** | -| n | n | n | In case of perfect hash function costs would be O(1)|
225+ | ** Binary Search Tree** | n | n | n | n | In case of balanced tree costs would be O(log(n))|
226+ | ** B-Tree** | log(n)| log(n)| log(n)| log(n)| |
227+ | ** Red-Black Tree** | log(n)| log(n)| log(n)| log(n)| |
228+ | ** AVL Tree** | log(n)| log(n)| log(n)| log(n)| |
229229
230230###Array Sorting Algorithms Complexity
231231
232- | Name| Best| Average| Worst| Memory| Stable| Comments|
233- | ---------------------| :--------- :| :--------- :| :------------- :| :-- -------:| :-------:| :--------|
234- | ** Bubble sort** | ` n ` | ` n^2 ` | ` n^2 ` | ` 1 ` | Yes| |
235- | ** Insertion sort** | ` n ` | ` n^2 ` | ` n^2 ` | ` 1 ` | Yes| |
236- | ** Selection sort** | ` n^2 ` | ` n^2 ` | ` n^2 ` | ` 1 ` | No| |
237- | ** Heap sort** | ` n log(n) ` | ` n log(n) ` | ` n log(n) ` | ` 1 ` | No| |
238- | ** Merge sort** | ` n log(n) ` | ` n log(n) ` | ` n log(n) ` | ` n ` | Yes| |
239- | ** Quick sort** | ` n log(n) ` | ` n log(n) ` | ` n ` <sup >` 2 ` </sup >| ` log(n) ` | No| |
240- | ** Shell sort** | ` n log(n) ` | depends on gap sequence| ` n (log(n)) ` <sup >` 2 ` </sup >| ` 1 ` | No| |
241- | ** Counting sort** | ` n + r ` | ` n + r ` | ` n + r ` | ` n + r ` | Yes| ` r ` - biggest number in array|
242- | ** Radix sort** | ` n * k ` | ` n * k ` | ` n * k ` | ` n + k ` | Yes| ` k ` - length of longest key|
232+ | Name| Best| Average| Worst| Memory| Stable| Comments|
233+ | ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:| :--------|
234+ | ** Bubble sort** | n | n< sup >2</ sup > | n< sup >2</ sup > | 1 | Yes| |
235+ | ** Insertion sort** | n | n< sup >2</ sup > | n< sup >2</ sup > | 1 | Yes| |
236+ | ** Selection sort** | n< sup >2</ sup > | n< sup >2</ sup > | n< sup >2</ sup > | 1 | No| |
237+ | ** Heap sort** | n log(n)| n log(n)| n log(n)| 1 | No| |
238+ | ** Merge sort** | n log(n)| n log(n)| n log(n)| n | Yes| |
239+ | ** Quick sort** | n log(n)| n log(n)| n <sup >2 </sup >| log(n)| No| |
240+ | ** Shell sort** | n log(n)| depends on gap sequence| n (log(n))<sup >2 </sup >| 1 | No| |
241+ | ** Counting sort** | n + r| n + r| n + r| n + r| Yes| r - biggest number in array|
242+ | ** Radix sort** | n * k| n * k| n * k| n + k| Yes| k - length of longest key|