Computational runtime: the concept silently constraining our lives

academics computer science

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.

Christopher is pursuing a Master's in Urban Planning at the Harvard University Graduate School of Design (GSD). Previously, he graduated from the University of Pennsylvania with a Bachelor's in Computer Science. He completed his MS in Engineering in Data Science at Penn as well.

Comments

topicTopics
academics study skills MCAT medical school admissions SAT college admissions expository writing English strategy MD/PhD admissions writing LSAT GMAT physics GRE chemistry biology math graduate admissions academic advice law school admissions ACT interview prep test anxiety language learning career advice premed MBA admissions personal statements homework help AP exams creative writing MD test prep study schedules computer science Common Application summer activities mathematics history philosophy organic chemistry secondary applications economics supplements research grammar 1L PSAT admissions coaching law psychology statistics & probability dental admissions legal studies ESL CARS SSAT covid-19 logic games reading comprehension PhD admissions engineering USMLE calculus mentorship Spanish parents Latin biochemistry case coaching verbal reasoning DAT English literature STEM admissions advice excel medical school political science skills AMCAS French Linguistics MBA coursework Tutoring Approaches academic integrity astrophysics chinese gap year genetics letters of recommendation mechanical engineering Anki DO Social Advocacy algebra art history artificial intelligence business careers cell biology classics dental school diversity statement geometry kinematics linear algebra mental health presentations quantitative reasoning study abroad tech industry technical interviews time management work and activities 2L DMD IB exams ISEE MD/PhD programs Sentence Correction adjusting to college algorithms amino acids analysis essay athletics business skills cold emails data science finance first generation student functions graphing information sessions international students internships logic networking poetry proofs resume revising science social sciences software engineering trigonometry units writer's block 3L AAMC Academic Interest EMT FlexMed Fourier Series Greek Health Professional Shortage Area Italian JD/MBA admissions Lagrange multipliers London MD vs PhD MMI Montessori National Health Service Corps Pythagorean Theorem Python Shakespeare Step 2 TMDSAS Taylor Series Truss Analysis Zoom acids and bases active learning architecture argumentative writing art art and design schools art portfolios bacteriology bibliographies biomedicine brain teaser campus visits cantonese capacitors capital markets central limit theorem centrifugal force chemical engineering chess chromatography class participation climate change clinical experience community service constitutional law consulting cover letters curriculum dementia demonstrated interest dimensional analysis distance learning econometrics electric engineering electricity and magnetism escape velocity evolution executive function fellowships freewriting genomics harmonics health policy history of medicine history of science hybrid vehicles hydrophobic effect ideal gas law immunology induction infinite institutional actions integrated reasoning intermolecular forces intern investing investment banking lab reports letter of continued interest linear maps mandarin chinese matrices mba medical physics meiosis microeconomics mitosis mnemonics music music theory nervous system