Performance graph Big(o) notation
Best is O(1)- constant & worst is O(n square)
Link to check Big(o) for different data structures - https://www.bigocheatsheet.com/
| Big O | Name | Description |
|---|---|---|
| 1 | Constant | statement, one line of code |
| log(n) | Logarithmic | Divide and conquer (binary search) |
| n | Linear | Loop |
| n*log(n) | Linearithmic | Effective sorting algorithms |
| n^2 | Quadratic | Double loop |
| n^3 | Cubic | Triple loop |
| 2^n | Exponential | Complex full search |
| Worst Case→ | Access | Search | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(n) | O(n) | O(n) | O(n) |
HashTable- implementation in C#/Python - [Dictionary<TKey, TValue>I), Java through HashMap
Hash functions converts Key to index/HashCode
Hash Collision: when Hash Function generates same function for to different Keys.
Queue -
- Enqueue - insert
- Dequeue - remove
- peek - shows the item
Stack -
- push - insert item on top of stack
- Pop - removes top item in the stack
- Peek - just shows top item in stack , does not remove it
| Sorting Algorithms | Space complexity | Time complexity | Time complexity |
|---|---|---|---|
| Worst case | Best case | Worst case | |
| Insertion Sort | O(1) | O(n) | O(n^2) |
| Selection Sort | O(1) | O(n^2) | O(n^2) |
| Bubble Sort | O(1) | O(n) | O(n^2) |
| Mergesort | O(n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n^2) |
| Heapsort | O(1) | O(n log n) | O(n log n) |
Comments
Post a Comment