Preferences

Code Theme

solarized light

login

Time and Space Complexity

Overview

As a software developer, it is important to be mindful of different aspects of your code. Such as: how correct the code is, ease of understanding, robustness to handle edge cases, how efficient it is, among other aspects. This last one is what we will focus on in this lesson.

Due to the importance of being able to measure how efficient a program is, specific notation has been developed to measure it. We can measure the best case scenario, the average case scenario and the worst case scenario. In most cases we are most interested in knowing how efficient our program is in a worst case scenario. Why is this? Because we as developers have no way of knowing how others will use our code, nor how it will handle at a much larger scale. We must assume that at some point, a worst case will be encountered and do our best to enable our code to run in even the most strenuous of cases.

There are two parts to complexity we can measure, being time complexity and space complexity. It is important to optimize for both of these as ignoring either might lead to disastrous consequences.

  • Time complexity measures how long the program takes to complete.
  • Space complexity measures how much of a systems resources a program takes.

    • Big O Notation

    The notation mentioned earlier in regards to worst case scenario is termed Big O notation.

  • Big O {phonetic: big-oh} represents the upper bound or worst-case scenario of a program.

    • That's all well and good, but how do we actually figure out what this might be for a program? By going through the program line-by-line, operation-by-operation and computing how long or how much space it takes. For most of this lesson we will focus on time complexity, however do know that everything mentioned holds true for space complexity as well.

    To an interpreter, an operation will take differing amounts of time. Some operations are easier than others. If an operation can be performed in constant time, that means that no matter what any variables might be in the operation, it won't affect how long it takes to perform. This would be if any variables in the operation have fixed size, such as integer or string. For example, assigning a value to a variable is easy, it can do this in constant time. If the operation is a conditional, this is also constant time. If an operation has constant time, then it has big O notation O(1). What about if the input is an unknown size?

    If we don't know the size of an input, we don't know how long it will take to perform some operation on it. This will be the case with datatypes such as array's and dictionaries. In this case, we represent this unknown with a random variable. A random variable could be something like x or n. Lets look at a few examples. If the operation is a for loop over an array, it will need to iterate through the array up to n times. If the operation is a while loop that breaks when it finds an element in a dictionary, this may take in the worst case n when the element is not in the dictionary. In both cases we may refer to them with big O notation O(n).

    Now how do we find the big O notation for a program? For each operation we either sum or multiply. If the current operation is independent of the previous, then we sum. If the next operation is dependent on the previous, then we multiply.

    Example

    1. We assign a variable to a constant value. This takes constant time; it also has constant space. Time: O(1) Space: O(1).
    2. We assign a variable to a constant value. This takes constant time; it also has constant space. Time: O(1) Space: O(1).
    3. We iterate through an array. We don't know how large this array is, so we should assign it a variable representing this unknown, such as n. Iterating through this array will take linear time. Since space has already been allocated for it, iterating through it won't take any additional space, thus constant space. Time: O(n) Space: O(1).
    4. Computing a conditional is no extra work. Time: O(1) Space: O(1).
    5. Appending a value to an array takes constant time. Things get a little more complicated about space. In the best case, the conditional will never evaluate to true, thus the space will be constant. In the worst case, the conditional will always evaluate to true, thus the space will be the same as the input. Because we are most concerned about what the worst case is, our space complexity will be the latter. Time: O(1) Space: O(n).
    6. We return an array. This takes constant time. Space is also constant as a previous step was responsible for its size. Time: O(1) Space: O(1).

    From this we should sum or multiply our complexity to find what the overall complexities are for this program.

    Time: O(1+ 1 + n * (1 + 1) + 1) = O(3 + 2n) ~= O(n)

    Space: O(1 + 1 + 1 * (1 + n) + 1) = O(4 + n) ~= O(n)

    Neat, so our program has linear time and linear space complexity. What happened to some of the terms? Why did we approximate at the end? Let's find out in the next lesson!