You may be surprised to hear that I declare computational runtime to be the silent constraint on our lives (compared to, say, money or conventional understandings of time). But much of the technology on which our modern world is built relies heavily on concepts of runtime.
In computer science, one way that we try to understand runtime conceptually is called Big O notation (because, well, there is an upper-case letter O). The principal idea here is that, as the size of the data in our tasks grows—let’s say to infinity, we can abstract out some sort of relationship between that size and the eventual runtime. As part of this process, any one-time “costs”—what in manual terms could be setting up the computer or in more technical terms could be additional tasks to set up or run the analysis—fade to the background. We are left with a raw understanding of how long on the order of magnitude the task will take.
To give an even more concrete—if simplistic—example, how long does it take to find an element in a sorted list?
If we have a list that’s sorted, with say n elements, the first thing we can do is look at the element in the middle. If the value we’re looking for is bigger, then we know we need to search the right half (and vice-versa if smaller). We can repeat this process. Every time, we are getting rid of half of the section that we are looking at. The amount of times we can do this is severely limited: if we have a list of length n, the partitions will be of size n/2, then n/4, then n/8, then n/16. In essence, we can only do this about log(n) times, plus or minus a few, before each partition only has one value (which we can compare). We call this operation O(log(n)), meaning the runtime is related on the order of magnitude of the log of the size of the input list, n.
When thinking about runtime, a huge constraint is called exponential runtime. In short, exponential runtime means that as the size of the data increases, the runtime is increasing exponentially (say, O(2^n)). What this also means is that, eventually, if the size of the data is big enough, exponential runtime will not finish in our lifetime. This could be very helpful for certain applications (think: security). But if the task is beneficial, this can be a huge hindrance and many heuristics exist to circumvent these runtime constraints.
Comments