Analysis of Loops

      

 Page No:-3

O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn't contain loop, recursion and call to any other non-constant time function.
// set of non-recursive and non-loo statements

For example swap() function has O(1) time complexity. A loop or recursion that runs a constant
number of times is also considered as O(1). For example the following loop is O(1).
// Here c is a constant
for (int i = 1;i <= C; i++)
//some O(1) expressions

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(nc): 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(n3) time complexity
for (int i = 1; i <=n; i += C)
 {
    for (int 1;j <=n;j+= C)
 {
   // some O(1) expressions
         }
  }
for (inti = 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) 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.
Main()
i= 1;
while(i < n)
 {
i = 2x i;
 }
}

In above code the statement inside the code runs logn times. Initially i value is 1 (i = 1). As the loop executes the value increases 2i, 22 i,23 i, and so all. And takes log n increment of i value to become   
equal to n.      
                                                               
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 (inti = n; i> 0; i = fun(i))
{
// some O(1) expressions
}

 Consecutive Loops 

When there are consecutive loops, we calculate time compiexity 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
}
Time complexity of above code is O(m)+O(n) which is O(m+n).

Check out the examples by clicking the next button