How to combine the time complexities of consecutive loops?
When there are consecutive loops, we calculate time complexity as a sum of the time complexities of individual loops.
To combine the time complexities of consecutive loops, you need to consider the number of iterations performed by each loop and the amount of work performed in each iteration. The total time complexity of the algorithm can be calculated by multiplying the number of iterations of each loop by the time complexity of each iteration and taking the maximum of all possible combinations.
For example, consider the following code:
for i in range(n):
for j in range(m):
# some constant time operation
Here, the outer loop performs n iterations, and the inner loop performs m iterations for each iteration of the outer loop. So, the total number of iterations performed by the inner loop is n * m, and the total time complexity is O(n * m).
In another example, consider the following code:
for i in range(n):
for j in range(i):
# some constant time operation
Here, the outer loop performs n iterations, and the inner loop performs i iterations for each iteration of the outer loop, where i is the current iteration count of the outer loop. The total number of iterations performed by the inner loop can be calculated by summing the number of iterations performed in each iteration of the outer loop, which is given by the formula sum(i) from i=1 to n, which is equal to n * (n + 1) / 2. Hence, the total time complex
Asymptotic Analysis of Algorithms Notes for GATE Exam [2024]Asymptotic Notations
This Asymptotic Analysis of Algorithms is a critical topic for the GATE (Graduate Aptitude Test in Engineering) exam, especially for candidates in computer science and related fields. This set of notes provides an in-depth understanding of how algorithms behave as input sizes grow and is fundamental for assessing their efficiency. Letâs delve into an introduction for these notes:
Table of Content
- Introduction of Algorithms
- Asymptotic Analysis
- Worst, Best and Average Case
- How to Analyse Loops for Complexity Analysis of Algorithms?
- How to combine the time complexities of consecutive loops?
- Algorithms Cheat Sheet for Complexity Analysis:
- Runtime Analysis of Algorithms:
- Little o and Little omega notations
- What does âSpace Complexityâ mean?
- Previous Year GATE Questions
Contact Us