Hello folks- Hope you’re doing well. Big-O notations are very useful approach to show the worst case time complexity of any operation or algorithm.
Big-O specifies the upper bound of a function in the asymptotic analysis and are widely used in the software development.
| Type | Symbol | Operation/ Algorithm | Number of operations (n= 10) | Execution Time (1 instruction/μsec) |
| Constant-time | O(1) | 1. Accessing Array Index (int a = empArray[5];) 2. Inserting a node in Linked List 3. Pushing and Popping on Stack 4. Insertion and Removal from Queue 5. Finding out the parent or left/right child of a node in a tree stored in Array 6. Jumping to Next/Previous element in Doubly Linked List | 1 | 1 μsec (μ= Micro) |
| Logarithmic | O(logn) | 1. Binary Search 2. Finding largest/smallest number in a binary search tree 3. Certain Divide and Conquer Algorithms based on Linear functionality 4. Calculating Fibonacci Numbers – Best Method The basic premise here is NOT using the complete data, and reducing the problem size with every iteration 5. Finding something in telephone book | 3.32 | 3 μsec |
| Linear algorithm | O(n) | 1. Linear Search 2. Traversing an array 3. Traversing a linked list 4. Deletion of a specific element in a Linked List (Not sorted) 5. Comparing two strings 6. Checking for Palindrome 7. Counting/Bucket Sort 8. Reading a book | 10 | 10 μsec |
| Super linear algorithm | O(nlogn) | 1. Merge Sort 2. Heap Sort 3. Quick Sort 4. Longest increasing subsequence | 33.2 | 33 μsec |
| Quadratic | O(n^2 ) | 1. Insertion Sort 2. Bubble Sort 3. Selection Sort 4. Traversing a simple 2D array | 102 | 100 μsec |
| Polynomial/ Cubic | O(n^c)/ O(n^3) | 1. Strassen’s Matrix 2. Multiplication Bucket Sort | 103 | 1000 μsec/ 1 msec) |
| Exponential | O(c^n)/ O (2^n) | 1. Tower of Hanoi | 1024 | 10 msec |
| Factorial | O(n!) | 1. Determinant Expansion by Minors/ Laplace expansion 2. Brute force Search algorithm for Traveling Salesman Problem 3. Generating all unrestricted permutations of a partially ordered set 4. Enumerating all partitions of a set | 10! = 3,628,800 | 3628.8 msec/ 3.6288 sec |
Hope you liked the post. Your valuable feedback is appreciated.
Techy Prakash 
Leave a comment