Big O Notation: Calculate Time & Space Complexity

Efficiency in algorithms is very important when it comes to scaling and sizing. Total execution time and space required for an algorithm can be the difference between a seamless experience and one that is laggy and robust. Let’s quickly run through a practical example, this is algo to calculate whether a number is prime or not.

In order to check if a number is prime we will loop through all numbers from 2 to but excluding the actual number and check its divisibility.

If we stick to numbers relatively tiny in size we can expect to return a result in a second or two. However, if we use a number like 27644437 this will take significantly longer it may even throw an error depending on the data type used to initialize the variable.

Big O notation is how programmers describe the performance of an algorithm. As a programmer we are concerned with the worst-case scenario, the really big prime number cases that will break our algorithms. With this in mind we will learn how to quickly calculate you the Big O notation of an algorithm.

As an algorithm grows in size its execution time can be expected to increase. Unless in the case of constants, these usually involve simple calculations without loops.

From the 1999 television-series “Big O”

How to calculate Big O

To calculate Big O, there are five steps you should follow:

1. Break your algorithm/function into individual operations
2. Calculate the Big O of each operation
3. Add up the Big O of each operation together
4. Remove the constants
5. The highest term will be the Big O of the algorithm/function

Simple, let’s look at some examples then.

public class Add
{
  public static void main(String[] args)
  {
    int num1 = 8; // initialize num1 to be 8
    int num2 = 4; // initialize num2 to be 4
    System.out.println(num1 + num2); // Output should be 12
  }
}
// Don't worry if you don't know Java syntax just know we are getting the sum of the two numbers

Our equation returns the sum of two variables that where initialized in the lines above it. There are 3 operations going each 0(1) which would be 0(3) but we remove the constants to calculate the complexity quickly. So the time complexity would be 0(1) or constant.

The time complexity is O(1) or constant time because the program doesn’t loop and the operations happen one time. No matter how big the numbers get it will still run one time.

Okay, so now let’s try a harder example.

public class NestedLoop
{
  public static void main(String[] args)
  {
    int x = 0; // This will increment and serve as the outer counter
    int y = 5; // This will decrement and serve as the inner counter
    
    while (x < 10)
    {
      System.out.println("Outer counter: " + x);
      while (y > 0)
      {
        System.out.println("Inner counter: " + y);
        y = y - 1;
      }
      x = x + 1;
    }
    System.out.println("Loop Completed.");
}

Now we could look at all the operations and evaluate each one time but we know we need the highest term and the constants are irrelevant. So lets find the highest term, a loop means that the program will run in its entirety until a condition is met.

This can quickly be accessed as 0(n). However, in order for this loop to resolve we need to look at the nested loop inside, which will also runs until its own condition is met.

0(n) * 0(n) = n²

Summary

Big O notation can be hard to understand but it comes up very often in interviews and scaling sizable solutions. The mark of a great programmer is understanding the limits of their builds and improve them. Solving a problem can seem frustrating enough but it is important to think about this ideas of run time and space required.

For more resources check out this links here, they helped me a lot in understanding this concept.

A Beginner's Guide to The Big O Notation | Hacker Noon

Know Thy Complexities!