Person A: Does this sound like a impossible task ?
Person B: No not really
Person A: Does it have limits ?
Person B: Yes it does, but you see dramatic difference in speed regardless.
Person A: This sounds like a scam. Is it a scam ? How much will this cost ?
Person B: No its not a scam, and its free.
Person A: So what is it ?
Person B: You just have to master runtime complexity 😊
Person A: What !? …. 😒
Person B: Yeah I know, I thought that too. But it works 😁
Person A: Yeahhhh well I never really understood that sort of stuff. I just implement businesses logic for living. I don’t know much about computer science. And I am not gonna waste my time on this. If I need speed, I’ll just deploy it on a bigger server 😒
Person A: Come on … Its easy. You don’t have to understand the computer science. You just need to understand graphs, and recognize patterns.
Person B: What … really ?
Person A: Yeah you just got to use the graph below. Or just Google something like “Runtime Complexity Graph” . All you got to know that things in Red are the danger zone, things in Orange are the “meh” zone, and things in the Yellowish Green zone are okay.
Person B: Wait what does this have to do with programming, and what about those function things ?
Person A: Oh yeah right. So those function things represent how your program can run. The “n” represents the input to your function, like an array objects, or numbers. In the danger zone, if you add just one more element, your time to completion more then doubles. Whereas in the Yellowish Green zone adding another element doesn’t do much of anything.
Person B: 😡 This still doesn’t help me.
Person A: Okay okay okay, how about I make cheat sheet for you ? Your little guide to spotting when your in the danger zone ?
Person B: Show me.
|Constant Time||1||No matter how many elements/ inputs you give your function. Its runtime will always stay the same.|
|Logarithmic Time||Log(n)||When doubling the number of input/elements into your function does not double the runtime. Also this is the runtime of most search algorithms.|
|Linear Time||n||When doubling the number of inputs/elements doubles your runtime. This is a for loop spanning from zero to the end of the input.|
|n + m||Two for loops one after the other, going over two different collections.|
|Quasi-linear Time||n *Log(n)||A worse version of Log(n). This is the runtime of most sorting algorithms.|
|Quadratic Time||n2||Every element in an array is compared with every other element in the input. This is the classic double “for loop” over a single array. For every nested “for loop” you add one more to the exponent. So if you had 5 nested for loops, you would have n5 .|
|n * m||Two nested for loops, but going over two different collections.|
|Exponential Time||2n||A single extra input doubles runtime. You never want this, ever.|