Analysis of Loops - Calculating Time Complexity

1) O(1): Time complexity of a function is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.

swap() function or loop or recursion that runs a constant number of timeshas O(1) time complexity.

Example:

for (int i = 1; i <= c; i++) {  // Here c is a constant   
        // some expressions
 }


2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.

Example:

for (int i = 1; i <= n; i += c) {   // Here c is a constant  
        // some expressions
}


3) O(n2) : Time complexity of nested loops is equal to the number of times the innermost statement is executed. Selection sort and Insertion Sort have O(n2)  time complexity.

Example:

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some expressions
       }
 }



4) O(Logn): Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. Binary Search has O(Logn) time complexity.

for (int i = 1; i <=n; i *= c) {
       // some expressions
}



5) O(LogLogn): Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.
 
for (int i = 2; i <=n; i = pow(i, c)) {  // Here c is a constant greater than 1   
       // some O(1) expressions
}
 

How to combine time complexities of consecutive loops?
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 expressions
}

for (int i = 1; i <=n; i += c) {
        // some 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 calculate time complexity when there are many if, else statements inside loops?
Worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case.

We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.

For example consider the linear search function where we consider the case when element is present at the end or not present at all.

When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.