How to make your program faster, regardless of programming language or hardware

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.

Person A:

Type FunctionDescription
Constant Time1No matter how many elements/ inputs you give your function. Its runtime will always stay the same.
Logarithmic TimeLog(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 TimenWhen doubling the number of inputs/elements doubles your runtime. This is a for loop spanning from zero to the end of the input.
n + mTwo for loops one after the other, going over two different collections.
Quasi-linear Timen *Log(n)A worse version of Log(n). This is the runtime of most sorting algorithms.
Quadratic Timen2Every 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 * mTwo nested for loops, but going over two different collections.
Exponential Time 2nA single extra input doubles runtime. You never want this, ever.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s