For Loop
Whenever we want to repeat a set of instructions we used loops. For loop is the most used in while, do-while and for.
Whenever a set of instructions repeats it has a very high impact on algorithm speed.
In the previous post, we tell that worst case is most often use, so we analyze our for loop in a worst-case scenario
Similarly, In this post, we are going to learn how to analyze for loop to calculate the running time of the algorithm
After all, we had already discussed asymptotic notation and we know the best case, average case, and worst case.
In this post, we discuss the basic time complexity of for by the help of simple examples.
For Loop Analysis
1. O(1) in for loop
The time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion, call to any other non-constant time function and any repetitive statements.
For Example add function
void add(int a,int b)
{
int sum = a+b;
cout<<sum;
}Another notable point is whenever a loop runs a constant number of time, it is treated as O(1). For Example,
for(int i = 0;i<C;i++) // C is constant
{
//O(1) expressions
}O(n)
Time Complexity of is considered as O(n) if variables are incremented/decremented by a constant amount. For example following functions have O(n) time complexity.
// Here c is a positive integer constant
for (int i = 1; i <= n; i = i + c) {
// some O(1) expressions
}
for (int i = n; i > 0; i = i - c) {
// some O(1) expressions
}O(n^c)
The time complexity of nested loops is equal to the number of times the innermost statement is executed.
For example, the following sample loops have O(n2) time complexity and another one is O(n^3)
for(int i =0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
// Some O(1) Expressions
}
}
for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
for(int k = 0;k<n;k++)
// Some O(1) expressions
}
}
}O(log(n))
Time Complexity of a loop is considered as O(log N) if the loop variables are divided/multiplied by a constant value.
for (int i = 1; i <=n; i = i* c) {
// some O(1) expressions
}
for (int i = n; i > 0; i = i / c) {
// some O(1) expressions
}O(log(log(n)))
Time Complexity of a loop is considered as O(log log N). If the variables are reduced/increased exponentially by a constant amount.
// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i,c)) {
// some O(1) expressions
}
Consecutive For Loop’s
When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.
for (int i = 1; i <=m; i += c) {
// some O(1) expressions
}
for (int i = 1; i <=n; i += c) {
// some O(1) expressions
}
The time complexity of the 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).
Time complexity when there are many if, else statements inside for loops?
As discussed earlier, the worst-case time complexity is the most useful among best, average and worst. Therefore we need to consider the worst case.
If there are any number of if-else condition then only we take if – else in consideration
For example, consider the linear search function where we considered the case when an element is present at the end or not present at all.
We can get an upper bound by ignoring if-else and other complex control statements,After all, when the code is too complex to consider all if-else cases,
