Day 4 of 30 days of Data Structures and Algorithms and System Design Simplified —Complexity Analysis
Complexity Analysis…
Welcome back peeps. Hope all’s well. It’s a lovely morning and before heading to my office, I wanted to finish complexity analysis as the day 4 of Data Structures and Algorithms series. So let’s get started!
In this post we will cover Complexity analysis as follows —
What is complexity Analysis?
Why Complexity Analysis is important?
Important concepts — Space and Time
Big — O notation and Examples
Tips and Techniques- How to determine and differentiate Complexities
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Let’s dive in!
Complexity Analysis
Importance : Very High
What is Complexity Analysis?
It’s a technique which is used to characterize the time taken by an algorithm with respect to the size of the input.
Complexities that are of prime importance are — Time Complexity and Space Complexity.
Space Complexity : The amount of Space require by an algorithm
Time Complexity : The amount of time required by an algorithm to execute
There are several ways to measure the complexity of an algorithm, including:
- Time complexity: This measures the amount of time an algorithm takes to run as a function of the input size. Common notation for time complexity is O(n), where n is the size of the input.
- Space complexity: This measures the amount of memory an algorithm uses as a function of the input size. Common notation for space complexity is also O(n), where n is the size of the input.
- Big O notation: This is a formal way to express the upper bound of an algorithm’s time complexity. It expresses the complexity in terms of the size of the input, and uses the symbol O to indicate that the time required grows no faster than the function inside the O.
- Big Omega notation: This is a formal way to express the lower bound of an algorithm’s time complexity. It expresses the complexity in terms of the size of the input, and uses the symbol Omega (Ω) to indicate that the time required grows no slower than the function inside the Omega.
- Big Theta notation: This is a formal way to express the exact bound of an algorithm’s time complexity. It expresses the complexity in terms of the size of the input, and uses the symbol Theta (Θ) to indicate that the time required grows at the same rate as the function inside the Theta.
Why Complexity Analysis is important?
An algorithms is a finite, unambiguous sequence of steps for solving a problem in a finite amount of space and time.
The efficient implementation of algorithms is incredibly important in computing and this is based on the choice of the data structures that you chose to use to solve the problem.
Important concepts — Space and Time
Space Complexity is the amount of memory required by an algorithm to run to its completion. Sometimes some algorithms are more efficient if the data is loaded depending on the requirement ( dynamic loading).
For example — Merge takes an extra n space O(n) whereas Selection sort, Insertion sort doesn’t take extra space and run in constant space O(1)
Time complexity is the number of steps it takes for an algorithm to reach its completion.
Big — O notation and Examples
Big O is about finding an asymptotic upper bound.
In simple words, Big O notation is a way to measure how well an algorithm scales as the amount of input data increases.
Big O notation is a way to express the upper bound of the running time complexity of an algorithm. It describes the worst-case scenario for the number of operations an algorithm will perform. Big O notation is often used to compare the efficiency of different algorithms for the same problem. The notation is generally written as O(n) where n represents the number of elements in the input.
Here are some common complexities expressed in Big O notation:
- O(1) represents a constant time algorithm, meaning the running time is always the same, regardless of the input size.
- O(log n) represents a logarithmic time algorithm, meaning the running time increases logarithmically with the input size.
- O(n) represents a linear time algorithm, meaning the running time increases linearly with the input size.
- O(n log n) represents a log-linear time algorithm, meaning the running time increases linearly with the input size, multiplied by the logarithm of the input size.
- O(n²) represents a quadratic time algorithm, meaning the running time is proportional to the square of the input size.
- O(2^n) represents an exponential time algorithm, meaning the running time doubles with each additional element in the input.
It is important to note that the big O notation only gives an upper bound of the running time and it does not give information about the lower bound of the running time. Also, the big O notation does not take into account the specific input data, it only considers the worst-case scenario.
It describes the algorithm complexity — the execution time required and the space used in the memory or disk by the algorithm.
Big O for time complexity is used to analyze the time complexity — the rough estimate of the no of steps an algorithm takes to reach to its completion.
- O(1) : Constant run time
Example : Select an item with an array index or key in dictionary
2. O(log N) : Logarithmic runtime
Example : Binary Search
3. O(n) : Linear runtime
Example : For loops and functions such as map(),reduce(),filter()
4. O(nlog N) : Linearithmic runtime
Example : Sort an array with Merge Sort. Heap sort, Quick Sort
5. O(n²) : Quadratic runtime
Example : 2 nested loops, bubble sort
6. O(2^n) : Exponential runtime
Example : Tower of Hanoi, TSP, Recursive Calculations
7. O(n!) : Factorial runtime
Example : Find permutations of given set of strings or numbers or TSP using brute force
Theta notation, written as Θ(f(n)), is a way to express the exact asymptotic complexity of an algorithm in terms of the size of the input. It is used to provide a tight bound on the running time of an algorithm, meaning that the running time of the algorithm is within a constant factor of the function f(n) for large inputs. In other words, the running time of an algorithm is both O(f(n)) and Ω(f(n)).
For example, if an algorithm has a running time of Θ(n²), it means that the running time of the algorithm is within a constant factor of n² for large inputs. This implies that the algorithm is both O(n²) and Ω(n²).
It is important to note that Theta notation only gives an exact bound on the running time of an algorithm in the case of large inputs. For small inputs, the running time of an algorithm can be much different than the function f(n) in Theta notation.
Tips and Techniques- How to determine and differentiate Complexities
Before hopping on to the tips and techniques, first understand what is best case and worst case complexity analysis.
Best Case Analysis
Best case analysis is about calculation the lower bound on the running time of an algorithm i.e calculate the time take to compute minimum no of operations.
For example — For a search ( linear), the best case is when the target element is present at the first location/index of the array. So the best case complexity comes out to be O(1) i.e the number of operations is constant in the best case.
Worst Case Analysis
Worst case analysis is about calculation the upper bound on the running time of an algorithm i.e calculate the time take to compute maximum no of operations.
For example — For a search ( linear), the worst case is when the target element is not present in the array and the algorithm searches/compares all the element of an array one by one. So the worst case complexity comes out to be O(n)
Now let’s discuss technique to calculate the complexity.
Pre-requisite : Drop all the constants and non dominant variables in your program
Step 1: Analyze and break the function in your program into single entity i.e into individual operations/steps
Step 2: Calculate the Big O of each operation one step at a time
Step 3: Add all the Big O of each operations ( calculated in step 2) together and calculate the end result.
When the loops are nested, we multiply the complexity of the outer loops by the complexity of the inner loop.
For example —
for i in range():
for j in range():
// Compute somethingThe complexity of inner loop is O(n) and of the outer loop is O(n) so the final complexity would be O(n²). If there are 3 loops running in accordance with each other then the complexity is O(n³) to run the program.
Rule of thumb —
For Sequential statements ( comparisons, assignments etc) the complexity is Constant O(1)
For Constant Time Loops, the complexity is Constant O(1)
For nested loops, the complexity depends on the number of loops ( as covered in the example above)
For Logarithmic time loops, the complexity is O(logN)
For recursive functions, the complexity ( worst case) is O(2^n)
Big O Complexity chart of Common Data Structure Operations
Here are the complexities of some famous data structures and algorithms:
- Arrays:
- Access: O(1)
- Search: O(n)
- Insertion: O(n) (if inserting at the beginning or middle)
- Deletion: O(n) (if deleting from the beginning or middle)
- Linked Lists:
- Access: O(n)
- Search: O(n)
- Insertion: O(1) (if inserting at the beginning)
- Deletion: O(1) (if deleting from the beginning)
- Stacks:
- Access: O(n)
- Search: O(n)
- Insertion: O(1) (push operation)
- Deletion: O(1) (pop operation)
- Queues:
- Access: O(n)
- Search: O(n)
- Insertion: O(1) (enqueue operation)
- Deletion: O(1) (dequeue operation)
- Hash Tables:
- Access: O(1) (average case)
- Search: O(1) (average case)
- Insertion: O(1) (average case)
- Deletion: O(1) (average case)
- Trees:
- Access: O(log n) (average case for balanced tree)
- Search: O(log n) (average case for balanced tree)
- Insertion: O(log n) (average case for balanced tree)
- Deletion: O(log n) (average case for balanced tree)
- Heaps:
- Access: O(n)
- Search: O(n)
- Insertion: O(log n)
- Deletion: O(log n)
- Sorting Algorithms:
- Bubble sort: O(n²)
- selection sort: O(n²)
- insertion sort: O(n²)
- merge sort: O(n log n)
- quick sort: O(n log n) (average case)
- heap sort: O(n log n)
- radix sort: O(nk)
That’s it for now. Day 5 : Backtracking Technique with most important questions coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
30 days of Data Analytics Series —
Day 1 : Data Analytics basics and kickstart of Data analytics with projects series
Day 3 : Data Analytics Ecosystem — Data Life Cycle, Data Analysis complete process ( most important things)
Day 5 : Statistics
Day 6 : Basic and Advanced SQL
Day 8 : Pandas and Numpy
Day 9 : Data Manipulation
Day 10 : Data Visualization — Part 1
Day 11 : Project 1 : Data Visualization — Part 2
Day 12 : Data Visualization — Part 3
Day 13: Tableau — Part 1
Day 14: Tableau — Part 2
Day 15: Tableau — Part 3
Day 16 : Data Analysis Project 2
Day 17 : Data Analysis Project 3
Day 18: Data Analysis Project 4
Day 20 : Data Analysis Project 6
Day 21 : Data Analysis Project 7
Take Complete Hands On Tableau Course : Link
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
