Some General Rules for Calculating Time Complexity

In this section we are going to see some general rules for calculating the time complexity. Sometimes calculating time complexity becomes very complicated , to avoid this, these rules are going to come handy.

A very important thing to keep in mind is that we always assume that the input size is very large.

Rule 1: Drop constant multipliers.

Eg: 

Using the above rule, we can drop the constant term.

Rule 2 : Drop lower order terms.

Eg:

We can further reduce this using rule 1.

∴ Worst case running time = O(n2 )

Rule 3: Running time of a program=  Running time of all fragments

Eg: Calculate the running time of the following program.

for (int i=0;i<n;i++)
{
    int a=5;
    a++;
}


for (int i=0;i<n;i++)
{
   for(int j=0;j<n;j++)
   {
   int b=5;
   b++;
   }
}

First of all we can break the program into 2 fragments. The first fragment is the first loop and the second fragment is the second loop (nested loop). Our final answer would be the sum of both fragments.

As we know running time for simple statements like declaration, assignment, arithmetic/logical operations is O(1).

Therefore the time complexity of the first fragment would be O(n), as the loop would run n times, the time complexity of the statements inside the loop is O(1).