[algorithm] How to find time complexity of an algorithm

Although there are some good answers for this question. I would like to give another answer here with several examples of loop.

• O(n): Time Complexity of a loop is considered as O(n) if the loop variables is 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 += c) {  
      // some O(1) expressions
  }
  
  for (int i = n; i > 0; i -= c) {
      // some O(1) expressions
  }
  

• O(n^c): 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(n^2) time complexity

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

  For example Selection sort and Insertion Sort have O(n^2) time complexity.

• O(Logn) Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.

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

  For example Binary Search has O(Logn) time complexity.

• O(LogLogn) Time Complexity of a loop is considered as O(LogLogn) if the loop variables is 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
  }
  //Here fun is sqrt or cuberoot or any other constant root
  for (int i = n; i > 0; i = fun(i)) { 
     // some O(1) expressions
  }
  

One example of time complexity analysis

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Analysis:

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

So the total time complexity of the above algorithm is (n + n/2 + n/3 + … + n/n), Which becomes n * (1/1 + 1/2 + 1/3 + … + 1/n)

The important thing about series (1/1 + 1/2 + 1/3 + … + 1/n) is equal to O(Logn). So the time complexity of the above code is O(nLogn).

Ref: 1 2 3