Big O Notation and Complexities

Programmers need a way to evaluate how “good” code is. This is useful for technical interviews and generally useful for becoming a more efficient coder. Three examples of ways to evaluate code are; how long does the code take to run, how much space does the code take, or how readable is the code. The last one is subjective, however the first two ways how definitive methods to define/evaluate them. More specifically, we’d like to examine time complexity and space complexity.

Time complexity is defined as the delta or change in the time of execution of the code depending on the change of the input. What does this mean? Why wouldn’t we just examine how the time it takes to execute the code? I will answer the second inquiry. If we were to examine a function that takes an input of “n” that outputs “n*n”, we’d be able to calculate the execution time by evaluating the time the code starts and the time the code is executed. However, this time isn’t consistent. The same console may output different times, different consoles may output different times, and when the code is executed almost instantaneously you are dealing with precise micro-measurements and differences that you may not be able to calculate correctly or efficiently.

Space complexity refers to the space required by the algorithm, not including space taken up by the inputs. Primitives like Booleans, numbers, null, etc. are constant space. Strings require O(n) of space where n is the length of the string and Reference types (arrays and objects) require O(n) of space where n is the length of the array or the number of keys in an object. O(n) is Big O Notation.

Big O Notation is how we define the complexity of the algorithm or code, examining the relationship between how the runtime grows as the inputs grow. An algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases. If the relationship in constant, the notation will be O(1), f(n) = 1. If the relationship is linear, the notation will be O(n), f(n) = n. And if the relationship is quadratic, the notation will be O(n2), f(n) = n2. There are even more relationships to examine, but these are the most common.