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
C++
//Here c is any positive constant for ( int i = 1; i <= m; i += c) { // some O(1) expressions } for ( int i = 1; i <= n; i += c) { // some O(1) expressions } // Time complexity of above code is O(m) + O(n) which is O(m + n) // If m == n, the time complexity becomes O(2n) which is O(n). //This code is contributed by Kshitij |
C
for ( int i = 1; i <= m; i += c) { // some O(1) expressions } for ( int i = 1; i <= n; i += c) { // some O(1) expressions } // Time complexity of above code is O(m) + O(n) which is O(m + n) // If m == n, the time complexity becomes O(2n) which is O(n). |
Java
for ( int i = 1 ; i <= m; i += c) { // some O(1) expressions } for ( int i = 1 ; i <= n; i += c) { // some O(1) expressions } // Time complexity of above code is O(m) + O(n) which is O(m + n) // If m == n, the time complexity becomes O(2n) which is O(n). // This code is contributed by Utkarsh |
C#
// Here c is any positive constant for ( int i = 1; i <= m; i += c) { // some O(1) expressions } for ( int i = 1; i <= n; i += c) { // some O(1) expressions } // Time complexity of above code is O(m) + O(n) which is O(m + n) // If m == n, the time complexity becomes O(2n) which is O(n). |
Javascript
for ( var i = 1; i <= m; i += c) { // some O(1) expressions } for ( var i = 1; i <= n; i += c) { // some O(1) expressions } // Time complexity of above code is O(m) + O(n) which is O(m + n) // If m == n, the time complexity becomes O(2n) which is O(n). |
Python3
for i in range ( 1 , m + 1 , c): # some O(1) expressions for i in range ( 1 , n + 1 , c): # some O(1) expressions # Time complexity of above code is O(m) + O(n) which is O(m + n) # If m == n, the time complexity becomes O(2n) which is O(n). |
How to Analyse Loops for Complexity Analysis of Algorithms
We have discussed Asymptotic Analysis, Worst, Average and Best Cases and Asymptotic Notations in previous posts. In this post, an analysis of iterative programs with simple examples is discussed.
The analysis of loops for the complexity analysis of algorithms involves finding the number of operations performed by a loop as a function of the input size. This is usually done by determining the number of iterations of the loop and the number of operations performed in each iteration.
Here are the general steps to analyze loops for complexity analysis:
Determine the number of iterations of the loop. This is usually done by analyzing the loop control variables and the loop termination condition.
Determine the number of operations performed in each iteration of the loop. This can include both arithmetic operations and data access operations, such as array accesses or memory accesses.
Express the total number of operations performed by the loop as a function of the input size. This may involve using mathematical expressions or finding a closed-form expression for the number of operations performed by the loop.
Determine the order of growth of the expression for the number of operations performed by the loop. This can be done by using techniques such as big O notation or by finding the dominant term and ignoring lower-order terms.
Contact Us