Algorithms are able to store or search large amounts of data and are very important in bioinformatics, such as researching genes or proteins in a large database. They can also be very useful for real-time GPS software -- Uber and Google Maps are able to update very quickly, allowing us to move around and call a ride efficiently. For very large databases, we need to optimize our algorithms to run our search quickly. When we assess different algorithms, we have to consider the computation complexity of different data structures.
Computational Complexity of Memory
In the 1990s, memory storage was very low. Since there aren’t infinite RAM supercomputers, memory is in high demand but low supply. And while nowadays, companies like Amazon and Microsoft are able to sell memory on aws or Azure, memory is still expensive; even with Mars rovers, memory needs to be stored on physical hardware, which can be heavy so its more exp
Now, memory can be more effective using GPUs. The CPU is single threaded, so it does computations one step at a time. But with thousands of single threads, a GPU can do computations at the same time. This is called parallelization. If problems can be parallelized, then it can be completed in much shorter time. In another way, opcodes are specific instructions on how to move memory, which can help optimize memory.
Computational Complexity of Programming Languages
There are different types of languages. Python uses an interpreter, so it reads a program line by line. However, programs like C have compilers and translate it into Assembly (0s and 1s). As a result, these programs must be compiled before (turn the program into Assembly) running. Generally, compiled languages are much faster than interpreter languages, although interpreter languages are simpler to code.
Computational complexity is a measure of the number of operations performed for an input of a certain size.
Here’s an example. Imagine that we want to take a number and return the number + 2. In order to do this, we have certain steps:
-
We take in a number.
-
We add the number with 2.
-
We return that number.
For every input, we have 3 operations. If we have 100 inputs, we would need 300 operations. And if we have 1,000 inputs, we would need 3,000 operations. As a result, the number of operations is always a constant number times the number of inputs. This means that our computation complexity is linear, or O(n), where we just have a constant time n (number of input).
Big-O notation is able to run the average run-time, which depends on the worst-case scenario (the longest run-time) for an input, while big-Theta notation can run the minimum number of run-time. Using these types of notation, we can use computational complexity to find the best types of data structures to use.
Let’s do an example! Let’s say we have an array of numbers: 1, 2, 3, 4, and 5 and we want to sum all the numbers in the array. We can do this simply by taking the first number, adding it to the second, adding it to the third, and then so on. But for n inputs, we would have at least n operations, resulting in a computational complexity of O(n). For memory, we have to make an extra variable (like sum). In order to optimize our memory, we can use the space we already have in the array by just changing the array to keep track of the sum (in place modifications). Another more efficient way would be to split our array in half, then split the two halves again, and then we can find all the pairs in the array, sum them, and then sum all these little sums in O(log(n)) time. This would be faster than either of the previous algorithms, which can help us sum and find information from a lot of data.
