Algorithm efficiency
In week two, I noted that there can be different algorithms for solving the same problem and that some alternative algorithms achieve the same result.
One important factor in choosing or designing an algorithm is its efficiency. There are different kinds of efficiency, such as financial cost and use of resources, but I will focus on time efficiency — the speed at which an algorithm will complete a task. You saw in week three how some sorting algorithms varied in efficiency.
Moore’s Law
Moore’s Law states that the number of transistors that can be fitted into the same space on an integrated circuit doubles around every two years. This means that computers are getting smaller and faster all the time.
Note that Moore’s Law isn’t a scientific formula, it’s just an observation of the trend of increasing computer power.
You might think that improvements in computer technology mean that it’s not important for algorithms to be efficient. The same code will run much faster on a modern computer than on a ten-year-old computer.
But, at the same time that computers are getting faster, computer scientists are finding more and more complex ways to use them. So algorithm efficiency continues to be as important as ever, perhaps more important.
Why is efficiency important?
When you write small demonstration programs, it doesn’t really matter whether your algorithm is efficient; on a modern computer you’ll get results very quickly.
However, in real-world applications, efficiency is very important.
A large program or application will have many algorithms. Inefficiency quickly adds up and programs become slow and unresponsive.
A recent trend in computing is ‘Big Data’, working with very large datasets. The efficiency of an algorithm often gets worse rapidly as the size of the dataset increases. Big Data requires us to come up with new algorithms, and efficiency is extremely important to be able to get results in a useful amount of time.
Users are very sensitive to delays. How would you feel if your favourite search engine became ten times slower?
Although computers are getting faster, we always expect them to do more. The need for efficient algorithms has not gone away.
Some applications are time critical. It doesn’t matter how accurately you can predict the weather for tomorrow if you can’t calculate it until the day after!
Many modern businesses rely on having the fastest algorithms, such as search and comparison engines, logistics companies, and companies doing financial forecasting and medical analysis.
Efficiency versus understandability
When you’re getting started with programming, it’s also important that algorithms are clear and simple to understand. While it’s important to consider efficiency, it’s not necessary to try and find the most efficient algorithm. This is a very hard task and a very efficient algorithm may be harder to understand.
Remember, you often need to return to your code and understand it in order to make changes, and other people may also need to work with your code.
Efficiency is only one factor in choosing or designing an algorithm.
Efficiency versus quality
Recall that you can also have alternative algorithms that give different results for the same problem. For example, different search engines return different results for the same query.
The search algorithms used by the major search engines are regularly changed and improved. Efficiency is very important for getting results back to searchers quickly, but the results need to be high quality. It’s no use returning poor results quickly.
When designing an algorithm, you often need to balance time efficiency with the quality of the results.
Can you think of any other examples of activities where you may need to make a trade-off between time efficiency and quality? Share your ideas in the comments!