How you can change the world by learning Data Structures and Algorithm? As a developer, you have the power to change the world! You can write programs that enable new technologies. For instance, develop software to find an earlier diagnosis of diseases.
But, that’s not the only way, you might do it indirectly by creating projects that make people more productive and help them free up time to do other amazing things. Whatever you do, it has the potential to impact the community who use it.
However, these accomplishments are only possible if we write software that is fast and can scale. Learning how to measure your code performance is the goal of this post.
First, let’s see a real story to learn why this is important.
An algorithm that saved millions of lives
During War World II, the Germans used AM radio signals to communicate with troops around Europe. Anybody with an AM frequency radio and some knowledge of Morse code could intercept the message. However, the information was encoded! All the countries that were under attack tried to decode it.
Sometimes, they got lucky and were able to make sense of a couple of messages at the end of the day. Unfortunately, the Nazis changed the encoding every single day!
A brilliant mathematician called Alan Turing joined the British military to crack the German “Enigma” code. He knew they would never get ahead if they keep doing the calculations by pen and paper.
So after many months of hard work, they built a machine. Unfortunately, the first version of the device took to long to decode a message! So, it was not very useful.
Alan’s team found out that every encrypted message ended with the same string: “Heil Hitler” Aha! After changing the algorithm, the machine was able to decode transmissions a lot faster! They used it the info to finish the war quicker and save millions of lives!
The same machine that was going to get shut down as a failure became a live saver. Likewise, you can do way more with your computing resources when you write efficient code. That is what we are going to learn in this post series!
Another popular algorithm is Page Rank developed in 1998 by Sergey Brin and Larry Page (Google founders). This algorithm was (and is) used by a Google search engine to make sense of trillions of web pages. Google was not the only search engine.
However, since their algorithm returned better results most of the competitors faded away. Today it powers most of 3 billion daily searches very quickly. That is the power of algorithm that scale!
So, why should you learn to write efficient algorithm?
There are many advantages; these are just some of them:
- You would become a much better software developer (and get better jobs/income).
- Spend less time debugging, optimizing and re-writing code.
- Your software will run faster with the same hardware (cheaper to scale).
- Your programs might be used to aid discoveries that save lives (maybe?).
Without further ado, let’s step up our game!
Algorithm (as you might know) are steps of how to do some task. For example, when you cook, you follow a recipe to prepare a dish. If you play a game, you are devising strategies to help you win. Likewise, algorithm in computers are a set of instructions used to solve a problem.Algorithm are instructions to perform a task
There are “good” and “bad” algorithm. The good ones are fast; the bad ones are slow. Slow algorithm cost more money and make some calculations impossible in our lifespan!
We are going to explore the basic concepts of algorithm. Also, we are going to learn how to distinguish “fast” from “slow” ones. Even better, you will be able to “measure” the performance of your algorithm and improve them!
How to improve your coding skills?
The first step to improving something is to measure it.
Measurement is the first step that leads to control and eventually to improvement. If you can’t measure something, you can’t understand it. If you can’t understand it, you can’t control it. And If you can’t control it, you can’t improve it.H. J. Harrington
How do you do “measure” your code? Would you clock “how long” it takes to run? What if you are running the same program on a mobile device or a quantum computer? The same code will give you different results, right?
To answer these questions, we need to nail some concepts first, like time complexity!
Time complexity
Time complexity (or running time) is the estimated time an algorithm takes to run. However, you do not measure time complexity in seconds, but as a function of the input. (I know it’s weird but bear with me).
The time complexity is not about timing how long the algorithm takes. Instead, how many operations are executed. The number of instructions executed by a program is affected by the size of the input and how their elements are arranged.
Why is that the time complexity is expressed as a function of the input? Well, let’s say you want to sort an array of numbers. If the elements are already sorted, the program will perform fewer operations.
On the contrary, if the items are in reverse order, it will require more time to get it sorted. So, the time a program takes to execute is directly related to the input size and how the elements are arranged.
We can say for each algorithm have the following running times:
- Worst-case time complexity (e.g., input elements in reversed order)
- Best-case time complexity (e.g., already sorted)
- Average-case time complexity (e.g., elements in random order)
We usually care more about the worst-case time complexity (We are hoping for the best but preparing for the worst).
Hope you like our this post also do read our other post.