05/10/2024
Big O Notation 101: The Secret to Writing Efficient Algorithms
From simple array operations to complex sorting algorithms, understanding the Big O Notation is critical for building high-performance software solutions.
1 - O(1)
This is the constant time notation. The runtime remains steady regardless of input size. For example, accessing an element in an array by index and inserting/deleting an element in a hash table.
2 - O(n)
Linear time notation. The runtime grows in direct proportion to the input size. For example, finding the max or min element in an unsorted array.
3 - O(log n)
Logarithmic time notation. The runtime increases slowly as the input grows. For example, a binary search on a sorted array and operations on balanced binary search trees.
4 - O(n^2)
Quadratic time notation. The runtime grows exponentially with input size. For example, simple sorting algorithms like bubble sort, insertion sort, and selection sort.
5 - O(n^3)
Cubic time notation. The runtime escalates rapidly as the input size increases. For example, multiplying two dense matrices using the naive algorithm.
6 - O(n logn)
Linearithmic time notation. This is a blend of linear and logarithmic growth. For example, efficient sorting algorithms like merge sort, quick sort, and heap sort
7 - O(2^n)
Exponential time notation. The runtime doubles with each new input element. For example, recursive algorithms solve problems by dividing them into multiple subproblems.
8 - O(n!)
Factorial time notation. Runtime skyrockets with input size. For example, permutation-generation problems.
9 - O(sqrt(n))
Square root time notation. Runtime increases relative to the input’s square root. For example, searching within a range such as the Sieve of Eratosthenes for finding all primes up to n.
Over to you: What else will you add to better understand the Big O Notation?
--
Subscribe to our weekly newsletter to get a Free System Design PDF (158 pages): https://bit.ly/3KCnWXq
hashtag hashtag hashtag
Credit: ByteByteGo
