| Data Structure | Access | Search | Insertion | Deletion | Comments |

| ----------------------- | :-------: | :-------: | :-------: | :-------: | :-------- |

| **Array** | 1 | n | n | n | |

| **Stack** | n | n | 1 | 1 | |

| **Queue** | n | n | 1 | 1 | |

| **Linked List** | n | n | 1 | 1 | |

| **Hash Table** | - | n | n | n | In case of perfect hash function costs would be O(1) |

| **Binary Search Tree** | n | n | n | n | In case of balanced tree costs would be O(log(n)) |

| **B-Tree** | log(n) | log(n) | log(n) | log(n) | |

| **Red-Black Tree** | log(n) | log(n) | log(n) | log(n) | |

| **AVL Tree** | log(n) | log(n) | log(n) | log(n) | |

| Name | Best | Average | Worst | Memory | Stable | Comments |

| --------------------- | :-------: | :-------: | :-----------: | :-------: | :-------: | :-------- |

| **Bubble sort** | n | n^2 | n^2 | 1 | Yes | |

| **Insertion sort** | n | n^2 | n^2 | 1 | Yes | |

| **Selection sort** | n^2 | n^2 | n^2 | 1 | No | |

| **Heap sort** | n log(n) | n log(n) | n log(n) | 1 | No | |

| **Merge sort** | n log(n) | n log(n) | n log(n) | n | Yes | |

| **Quick sort** | n log(n) | n log(n) | n^2 | log(n) | No | |

| **Shell sort** | n log(n) | depends on gap sequence | n (log(n))^2 | 1 | No | |

| **Counting sort** | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |

| **Radix sort** | n * k | n * k | n * k | n + k | Yes | k - length of longest key |