Time Complexity vs Space Complexity

This is going to be an interesting article, which will tell you why you should care about time and space complexities.

Sometimes, there is more than one way to solve the problem. We need to learn how to compare the performance of different algorithms and choose the best one to solve a particular problem. While analyzing an algorithm, we mostly consider time complexity and space complexity.

Time Complexity:

The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.

So, how do we find the time complexity of an algorithm or our solution?

We will analyze complexity using Big-O notation in this article,

Big-O notation

The big-O notation is the language we use for talking about how long an algorithm takes to run. It’s how we compare the efficiency of different approaches to a problem.

In big-O notation, we express the runtime in terms of how quickly it grows relative to the input, as the input gets arbitrarily large.

Let’s break that down:

1. how quickly the runtime grows — It’s hard to pin down the exact runtime of an algorithm. It depends on the speed of the processor, what else the computer is running, etc. So instead of talking about the runtime directly, we use big O notation to talk about how quickly the runtime grows.
2. relative to the input — If we were measuring our runtime directly, we could express our speed in seconds. Since we’re measuring how quickly our runtime grows, we need to express our speed in terms of…something else. With Big-O notation, we use the size of the input, which we call “n.” So we can say things like the runtime grows “on the order of the size of the input” O(n) or “on the order of the square of the size of the input” O(n²).

Let’s look at some examples.

public static void printFirstItem(int[] items) {
    System.out.println(items[0]);
}

This method runs in O(1) time (or "constant time") relative to its input. The input array could be 1 item or 1,000 items, but this method would still just require one step.

public static void printAllItems(int[] items) {
    for (int item : items) {
        System.out.println(item);
    }
}

This method runs in O(n) time (or "linear time"), where n is the number of items in the array. If the array has 10 items, we have to print 10 times. If it has 1,000 items, we have to print 1,000 times.

public static void printAllPossibleOrderedPairs(int[] items) {
    for (int firstItem : items) {
        for (int secondItem : items) {
            System.out.println(firstItem + ", " + secondItem);
        }
    }
}

Here we're nesting two loops. If our array has n items, our outer loop runs n times and our inner loop runs n times for each iteration of the outer loop, giving us n^2 total prints. Thus this method runs in O(n^2) time (or "quadratic time"). If the array has 10 items, we have to print 100 times. If it has 1,000 items, we have to print 1,000,000 times.

Space Complexity:

The space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or “space complexity”) is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we’re allocating.

This method below takes O(1) space (we use a fixed number of variables):

public static void sayHiNTimes(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println("hi");
    }
}

This method below takes O(n) space (the size of ‘tempArray’ scales with the size of the input):

public static String[] arrayOfHiNTimes(int n) {
    String[] tempArray = new String[n];
    for (int i = 0; i < n; i++) {
        hiArray[i] = "hi";
    }
    return hiArray;
}

Usually, when we talk about space complexity, we’re talking about additional space, so we don’t include space taken up by the inputs. For example, this method takes constant space irrespective of its size.

public static int getLargestItem(int[] items) {
    int largest = Integer.MIN_VALUE;
    for (int item : items) {
        if (item > largest) {
            largest = item;
        }
    }
    return largest;
}

Sometimes there’s a tradeoff between saving time and saving space, so you have to decide which one you’re optimizing for.

I hope you learned something from this article, see you guys in other ones.