New computers seem to run any program without a problem. In addition, we can see computers with 1 TB Solid State Drives, up to 32 GB Memory, and Multicore Graphic Cards, among other excellent features.
No matter how fast computers might be, they are not infinitely fast, and their memory is not free. Computers, therefore, are bounded to physical resource constraints. As a Software Engineer, you should consider a computer’s physical load due to an implemented algorithm and the space it consumes.
Time Complexity
Suppose you must deliver a huge file. You have two options: take the file with you to its recipient or transfer it electronically. Depending on the delivery method, your “delivery” algorithm will change.
Let’s think about the electronic transfer method. First, the algorithm might bind to the file’s size, so you might think that somehow the computational steps or processes have something to do with it. So let’s ignore the simplification process and assume that the transfer is a function of the file’s size. Also, let’s call this function $O$. So our electronic transfer would roughly be $O(s)$, being $s$ the file’s size.
What about the physical delivery method? Suppose you have to drive to the recipient’s address and there is no traffic jam, and you go at a regular speed. In this case, it doesn’t matter how large the file is. It could be 10 MB or 1 TB. You know you will take the same time bringing one or the other. In this case, our delivery function would be independent of the file’s size and could be something like $O(1)$.
You might be wondering why we are talking about time complexity and not considering the time for the physical delivery case. It is true that while you drive to the recipient’s address, traffic can change, or you can decide to go slower or faster and thus affecting the time you reach your destination. However, we can set our first definition for computational runtime complexity as the amount of computer time needed to complete an algorithm. This computational time often estimates the number of operations performed by the algorithm.
Asymptotic Notation
Let’s consider two quadratic functions. Let’s have $f(n) = n^{ 2 }+n+\frac{1}{2}$ and $g(n) = n^2$.
We could quickly infer that both functions’ behavior is the same despite $f(n)$ being different from $g(n)$. We could argue that the effect on the function behavior is given by its higher degree (i.e., $n^{ 2 }$ increases the function value more than $n$ does). So we could simplify things here and say that $f(n)$ and $g(n)$ have the same asymptotic behavior: $n^2$. The actual reason for this abstraction is to analyze the order of growth or rate of growth of the running time that interests us.
Simplification Rules
Drop Constants
We can drop constants since factors are less significant than the actual growth rate in determining computational efficiency for large inputs. Some examples here.
- $O(34 \cdot n^{2})$ becomes $O(n^{2})$
- $O(n+n)$ becomes $O(2 \cdot n)$ becomes $O(n)$
Many people resists that though, because they argue $O(2 \cdot n)$ is more “precise” than $O(n)$, but they are not.
Consider the following codes.
Min and Max v1 $O(n)$
1let min = Number.MAX_SAFE_INTEGER;
2let max = Number.MIN_SAFE_INTEGER;
3for(let x of array) {
4 if(x < min) min = x;
5 if(x > max) max = x;
6}
Min and Max v2 $O(2n)$
1let min = Number.MAX_SAFE_INTEGER;
2let max = Number.MIN_SAFE_INTEGER;
3for(let x of array) {
4 if(x < min) min = x;
5}
6for(let x of array) {
7 if(x > max) max = x;
8}
Which one is faster? Consider that the number of instructions for multiplication requires more steps than addition at assembly level. Somehow the computer must perform a sort of optimization.
The only thing that would make us choose between v1 and v2 would be that v1 has less code lines making it more readable.
Drop Non-Dominant terms
Let’s consider our function $f(n) = n^{2} + n + \frac{1}{2}$. Lower-order terms are relatively insignificant for large values of $n$. Thus, getting an asymptotic behavior of $f(n) = n^{2}$. Some examples here.
- $O(n^{2} + 3n + \frac{1}{3})$ becomes $O(n^{2})$
- $O(n + \log(n))$ becomes $O(n)$
- $O(5 \cdot 2^{n} + 1000 \cdot n^{100})$ becomes $O(2^{n})$
The following graphic depicts some common functions’ growth rates.
Multipart algorithms: Addition vs. Multiplication
Let’s consider the following code, where A.length !== B.length.
1for(let a of A) {
2 console.log(a);
3}
4
5for(let b of B) {
6 console.log(b);
7}
The computational effor here is determined by the amount of work over A and the amount of work over B. Thus, the runtime complexity is $O(A+B)$.
Let’s consider the following code, where A.length !== B.length.
1for(let a of A) {
2 for(let b of (B)) {
3 console.log(`A: ${a} | B: ${b}`);
4 }
5}
The computational effort here is determined by the amount of work done over B for each element in A. Thus, the runtime complexity is $O(A * B)$.
What would the runtime complexity of the following code?
1for(let a of A) {
2 for(let b of (B)) {
3 console.log(`A: ${a} | B: ${b}`);
4 }
5 for(let b of (B)) {
6 console.log(`A: ${a} <=> B: ${b}`);
7 }
8}
We could think of $O(A * (B + B))$, by simplification we would get $O(A * 2B)$, and finally $O(A * B)$.
Big O Notation $O$
Big O is a notation that describes an upper bound on the runtime. We could think of it as a mathematical less-than-or-equal relationship. Let’s consider what $O(n^{2})$ does mean: The algorithm is at least as fast as $n^{2}$. We could not surpass that behavior because $n^{2}$ would be the upper limit. It also implies that a quadratic behavior would enclose a linear behavior (i.e., $n \leq n^{2}$).
Big Omega Notation $\Omega$
Big Omega is a notation that describes a lower bound on the runtime. We could think of it as a mathematical greater-than-or-equal relationship. For example, let’s consider what $O(\log(n))$ does mean: The algorithm won’t be faster than that. We can find ways to optimize algorithms, but those algorithms have their $\Omega$, and we know they cannot go faster than that. For instance, printing all the elements of an array is $\Omega(n)$ because we need to “touch” all the elements in the array.
Big Theta Notation $\Theta$
Big Theta is a notation that describes a tight bound on the runtime. So we could think of it as a “sandwich.” It’s a behavior intended to be both $O$ and $\Omega$ simultaneously. But, curiously, the way the industry tends to refer to $\Theta$ is $O$.
Bibliography
- Introduction to Algorithms1