Introduction to Algorithm Complexity Analysis and Big-O Notation

Hi everyone,

In this article, we are going to make an introduction to Algorithm Complexity and Big-O Notation topics. After reading this article, you will look at the algorithms you develop differently and hopefully you will be able to write more efficient code.

Let's say you are given the choice of cleaning a room with a toothbrush or a vacuum cleaner. Which one would you prefer? In most cases, you probably would choose the vacuum cleaner. Using a vacuum cleaner sounds like less work than using a toothbrush. Mostly, yes. However, if the room is in a child's toy, it may be easier to use the toothbrush.

Let's say this time you are given the choice of multiplying two numbers together by using a pen and paper or a calculator. In most cases, again, you would pick the calculator, since it is faster and requires less work. But, if you can easily multiply these numbers without using a calculator, it is unnecessary and more work to use it.

What do these examples have in common? And what do they have to do with computer science (CS) ? In each of the situations mentioned above, one of the choices seems to involve significantly less work. However, measuring the amount of work required is very difficult since there are unknowns: The size of the room, values of the numbers to be multiplied, etc.

In each case, the unknown information relates to the size of the problem. Especially if the problem is easy (for example, multiplying 2 by 3), our original approach, using a calculator, is not very efficient. Of course, our intuition is usually correct, because most of the problems are reasonably large.

In CS, we need a way to measure the amount of work done by an algorithm relative to the size of a problem, since usually there are more than one algorithm is available to solve any given problem. Ideally, we would like to choose the most efficient algorithm. That algorithm does the least work for a problem and usually takes less time to complete.

The amount of work involved in executing an algorithm relative to the size of the problem is the algorithm’s complexity. As programmers, we would like to be able to determine the complexity of an algorithm before or after developing it. Then we could find the most efficient solution (faster or requires less work) for the problem.

But, how do we measure the amount of work required to execute an algorithm?

We use the total number of steps executed as a measure of work. One statement, may require only one step; another statement, such as a loop,may require many steps. Given an algorithm with just a sequence of simple statements (no branches or loops), the number of steps performed is directly related to the number of statements. When we introduce branches, however, it becomes possible to skip some statements in the algorithm.

Branches allow us to divide the algorithm into sections without physically removing them from the algorithm because only one branch executes at a time. Since we usually want to express work in terms of the worst-case scenario, we use the number of steps in the longest branch.

Now consider the following for loop:


 int a=98;
 for(int i=0;i<300;i++){
  a=a+2;
  a=a-2;
 }

If it repeats a sequence of 2 simple statements 300 times, it performs 600 steps. Loops allow us to multiply the work done in an algorithm without physically adding statements. Now that we have a measure for the work done in an algorithm, we can compare the following algorithms. Suppose, for example, that Algorithm X always executes 565 steps and Algorithm Y always does the same task in 983 steps. Then we can easily say that Algorithm X is more efficient because it takes less steps to complete the same task.

In order to express the complexity of an algorithm computer scientists have come up with a name, Big-O notation. In Big-O notation, we express the complexity by putting the highest-order term in parentheses with a capital O in front. For example, O(1) is constant time; O(N) is linear time; O(N^2) is quadratic time; and O(N^3) is cubic time.

Constant Complexity (Big-O Notation: O(1))

If an algorithm, always takes the same number of steps or fewer,we say that it executes in constant time. These algorithms are said to have constant time complexity. But, constant time doesn’t mean small; it just means that the amount of work done does not exceed some amount from one run to another regardless of the size of the problem.

If a loop executes a fixed number of times, the work done is greater than the physical number of statements but is still constant.

Linear Complexity (Big-O Notation: O(N))

What happens if the number of loop iterations changes from one run to the next? In this case, the variable N determines the size of the problem. If we have a loop that executes N times, the number of steps to be executed is some factor times N. This factor is the number of steps performed within a single iteration of the loop. Specifically, the work done by an algorithm with a loop is given by the expression:

Mathematicians call expressions of this form linear and algorithms such as this one are said to have linear time complexity. Notice that if N grows very large, the term (A x N) dominates the execution time. That is, B becomes an insignificant part of the total execution time. For instance, if A and B are each 20 steps, and N is 5,000,000, then the total number of steps is 100,000,020. The 20 steps contributed by B represent only a tiny fraction of the total in this case.

Quadratic Complexity (Big-O Notation: O(N^2))

Consider a nested loop.


        int a=1;
 for(int i=0;i<N;i++){
  for(int j=0;j<N;j++){
   a=a+2;
   a=a-2;
  }
 }

The number of steps in the inner loop, and the number of iterations performed by the inner loop, must be multiplied by the number of iterations in the outer loop. If the number of iterations performed by the inner loop is equal to the number of iterations in the outer loop, N. Then the algorithm is said to have quadratic time complexity (N^2).

If the size factor N is small, the constants and lower-order terms in the complexity expression may be significant.

Example: To see how this idea works, let’s look at an example.

Suppose that Algorithm X is O(N^2) and that Algorithm Y is O(N). For large values of N, we would normally choose Algorithm Y because it requires less work than X. But suppose that in Algorithm Y, A = 1,000 and B = 1,000. If N = 1, then Algorithm Y takes 2,000 steps to execute. Now suppose that for algorithm X, A = 10, B = 10, and C = 10. If N = 1, then Algorithm A takes only 30 steps to execute. So for N=1, we can say that Algorithm X is more efficient than Y. However, if N goes to infinity, Algorithm Y becomes more efficient than X.

Logarithmic Complexity (Big-O Notation: O(logN))

An algorithm is said to take logarithmic time if T(n) = O(log n). Due to the use of the binary numeral system by computers, the logarithm is frequently base 2. However, by the change of base for logarithms, logaN and logbN differ only by a constant multiplier, which in big-O notation is discarded; thus O(log n) is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search. In binary search, you decide which half it's in, based on looking at the median of a sorted list. Then you divide that in two. Then you divide that in two. And so on.. It's O(log n) because, if you look at it backwards: You take one, multiply it by two, multiply it by two again, and so on. The logarithm is the opposite of exponentiation.

An O(log n) algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.

Here is an example to O(logn) complexity:


     while (n > 0) {  
         n/=2;  
     }

Big-O Complexity Types Comparison

Time Complexity of Common Data Structure Operations

Chart Source: http://bigocheatsheet.com/

I would like to finalize this post by giving a memorable example to complexity analysis:

Let's just say I'm in front of a class of students and one of them has my pen. Here are some ways to find the pen and what the O order is.

O(n^2 ): I question a student and ask them, "Does Jeff have the pen? No? Does Bob have the pen?" And so on, naming each student. If I don't get the answer from the first student, I move on to the next one. In the worst case I need to ask n^2 questions - questioning each student about each other student.

O(n): I ask each student if they have the pen. If not, I move on to the next one. In the worst case I need to ask n questions.

O(log n): I divide the class in two, then ask: "Is it on the left side, or the right side of the classroom?" Then I take that group and divide it into two and ask again, and so on. In the worst case I need to ask log n questions.

I might need to do the O(n^2 ) search if only one student knows on which student the pen is hidden. I'd use the O(n) if one student had the pen and only they knew it. I'd use the O(log n) search if all the students knew, but would only tell me if I guessed the right name.

O(1): Which one of you have my pen?

This example finalizes the article, but here are some other exercises for you to test yourself:

Find the time complexities of the following exercises:


public class Main {
 public static void main(String[] args) {
        
  int n = 6; 
                
  // First Exercise
  int count = 0;
  for (int i = 1; i <= n; i++)
   for (int j = n; j > 1; j = j - 3)
    for (int k = 1; k < n; k = k + 2)
     count++;
  System.out.println(count);

  
  
  // Second Exercise
  count = 0;
  for (int i = 1; i <= n; i++)
   for (int j = n; j > 1; j = j - 3)
    for (int k = 1; k < 1000; k = k + 2)
     count++;
  System.out.println(count);

  
  
  // Third Exercise
  count = 0;
  for (int i = 1; i <= 1000; i++)
   for (int j = i; j > 999; j = j - 3)
    for (int k = 1; k < 1000; k = k + 2)
     count++;
  System.out.println(count);

  
  
  // Fourth Exercise
  count = 0;
  int j = 1;
  for (int i = 1; i < n; i++) {
   while (j < n) {
    j++;
    count++;
   }
   j = 1;
  }
  System.out.println(count); 

  
  
  // Fifth Exercise
  count = 0;
  int N = 1024;
  while (N > 1) {
   count++;
   N = N / 2;
  }
  System.out.println(count);
 }
}

Please share the post to access the answers. The answers are available here:

Click to Download The Answers

I hope you enjoyed this post, if so, please share and leave a comment below. Thank you for reading and happy coding!