Big-O and Time Complexity

What is Big-O Notation?

The Big-O notation is used to depict an algorithm’s growth rate and specifies the upper bound of an algorithm’s performance. It basically depicts the relation between the order of magnitude of the algorithm and its effect on the number of operations required.

For example, if I say an algorithm takes O(n2) time, this means that the algorithm will carry out its task taking at the most N2 steps for input size N.

This is helpful for us because when we write a program, we test them on small inputs. What if the user runs our program on a larger input. So, the run time analysis helps us to predict how our program will be in the real world.

How to describe the growth rate of an algorithm?

While describing the growth rate of an algorithm, we consider the term that is going to affect the most on the algorithm’s performance. This term is called as the dominant term.

For example, the performance of an algorithm of a quadratic equation an2 + bn + c (where a, b and c are constants).

The maximum impact on the algorithm’s performance will be on an2. Hence, we can say that the algorithm has performance O(N2).

How to compute the complexity of an algorithm?

1. Select the computational resource you want to measure, i.e. time and memory.

2. Look for loops or recursion. Try finding conditions that make the algorithm work (size of input).

3. Once you have the size, try to find the best case, worst case and the average case.

What is time complexity?

The time complexity is the number of operations an algorithm performs to complete its task. The number of operations to be performed by the algorithm are indicated by the length of the input.

Calculation of time complexity of several codes -

1. Loops — The running time of a loop is equal to the running time of statements inside the loop multiplied by the number of iterations.

For example,

for(i=1, i<=n; i++) 
{
  m=m+2;
}

Here the loop is executed n times and the statement took time c. So, the total time taken by the above loop will be

total time = c*n that is O(n).

2. Nested loops — The total running time is the product of the sizes of all the loops.

For example,

for(i=1, i<=n; i++) 
{
  for(j=1, j<=n; j++) 
    {
      m=m+1;
    }
}

Here, the outer as well the inner loop is executed n times each where the statements took constant time c. So, the total time will be

Total time = c*n*n that is O(n2).

3. Consecutive statements — In this we simply add the complexities of each statement.

For example,

x=x+1;                 //takes constant time c0
for(i=1, i<=n; i++)    //loop executes n times and has constant time c1
{
  m=m+2;
}
for(i=1, i<=n; i++)   //inner and outer loop both executes n times each 
  {                       // statements take constant time c2.
    for(j=1, j<=n; j++) 
      {
        m=m+1;
      }
  }

Here, the total time taken by the code will be,

Total time = c0 + c1 n + c2 *n² that is O(n²).

4. If-else statements — We consider the worst case run time that means, we consider the time taken by the if part as well as the else part.

For example,

s = sakshi
if ( s.length() == 6)                     //takes constant time c0
  return a;                                  //takes constant time c1
else 
(
  for(i=1, i<=n; i++)           //takes (constant c2 + constant c3) * n
    { 
      if (int i = 0; i<=s.length(); i++) 
      //takes c2 for test and c3 for no else part
      return b;
    } 
 )

Here, total time taken by the code will be

Total time = c0 + c1 + ( c2 + c3 ) * that is O(n).

5. Logarithmic complexity — It means that an algorithm’s performance time has logarithmic factor.

For example,

int a = 10;
for(i=a, i>=0; i=i/2)
  {
    System.out.println(i);
  }

Here, the time taken will be O(logn) because it takes a constant time to cut a problem size by ½.

Note — A constant time that is O(1) is better than a linear time which is O(n) because the former is not depending on the input size of the problem.

So, the order is always,

O(1) > O(log n) > O(n) > O(n log n) > O(n² ) > O(2^n)