How to determine time complexity of an algorithm

      There are some general rules to determining the running time of an algorithm.
Below are few Example

Loops

---

      The running time of a loop at most, the running time of the statements inside the loop multiplied by the number of iterations.

for (i=0; i<=n; i++) 

{

 total = total + 1;   // constant statement 'c'

}

Total time =  constant x n = c x n = O(n)

Nested loops

---

 Total running time of the sizes of all the loops(inside to out).

//outer loop executed n times
for (i=1; i<=n; i++) {
      // inner loop executed n times 
       for (j=1; j<=n; j++) 
       {
             k = k+1; //constant time 'c'
        } 
}


Total time = c x n x n = cn² = O(n²)

Consecutive statements

---

x = x +1; //constant time 'c'

// executed n times
for (i=1; i<=n; i++)
{
    m = m + 2; //constant time 'c'
}

//outer loop executed n times
for (i=1; i<=n; i++)
    {
     //inner loop executed n times
      for (j=1; j<=n; j++)
      {
       k = k+1; //constant time 'c' 
      }
}

Total time = c + cn + cn² = O(n²) 

If else statements

---

if (length ( ) != otherStack. length ( ) )
{
return false; // constant

}
else
{
// else part: (constant + constant) * n
for (int n = 0; n < length( ); n++)
{
// another if : constant + constant (no else part)
if (!list[n].equals(otherStack.list[n]))
//constant
return false;
}

}

Total time = c + c + (c + c) * n = O(n)

Logarithmic complexity

---

 An algorithm it takes a constant time to cut the problem size by a fraction.

Example

for (i=1; i<=n;) 
{ 
i = i*2; 
}

Initially i = 1, next step i = 2, then i = 4 and so on.

Let us assume that the loop is executing K times

K^th step 2ⁱ = n   come out of the loop

log(2ⁱ) = logn
ilog2 = logn
i = logn

So the total time = O(logn)