Complexity Analysis

Often times there are many solutions to a problem and choosing the best or optimal solution depends on how it performs and the resources it consumes.The performance and efficiency of a program or an algorithm is measured by two complexity measures, time complexity and space complexity.

For this analysis lets consider an example of adding all the values in a list using a loop.

def sum_of_list(int_list):
    total = 0
    for val in int_list:
        total = total + val
    return total

Time Complexity

• It is the amount of time taken by the algorithm to complete its process as a function of its input length, n. It is not the execution time of the machine on which the algorithm is running on.
• To calculate time complexity, it is assumed that a constant time is taken to execute one operation and the total operations for an input length of n are calculated.
• It is commonly expressed using asymptotic notations, Big O - O(n), Big Theta and Big Omega with Big O being often used.
• In the above example, line 2 gets executed one time i.e. O(1) and line 3 is loop and line 4 gets executed n times i.e. O(n). Since the worst case is taken the time complexity here is O(n).

Space Complexity

• Space complexity is a function, describing the amount of memory or space an algorithm takes in terms of the amount of input to the algorithm.
• It includes both space used by the input and any auxiliary extra space used by the algorithm while it is being executed.
• It is commonly expressed using Big O notations - O(n). If the input vary in size say an array, the space complexity depends on the size of the array and hence cannot be less than O(n). For fixed size inputs, the complexity will be constant O(1).
• In the above example, we need space to store the result total and lets say 4 bytes and we need to store the input which could be n * 4 bytes. So the worst case is taken and the space complexity here would be O(n).

Big-O Complexity Chart

In general, time complexity is more important than the space complexity as time taken to compute cannot be shortened easily and compute cost more with storage and memory getting cheap now a days.