Lesson 5: Optimization

Time Complexity

  Time complexity is a measure we can use to tell exactly how optimized a certain algoritm is or is not. Since

is a numerical measurement of the computational strain that an algorithm puts on the processor it is running on, it is an incredibly useful tool in understanding how to optimize code.

An example using sorting algorithms:

Here is an example using two different sorting algorithms: Bubble Sort and Quick Sort

Although these two algorithms do essentially the same thing, one has a lower time complexity which makes it more optimized than the other. Selection Sort has an average time complexity of θ(n^2) while Quick Sort has one of only θ(n log(n)).

Time complexity does not measure the exact time that an algorithm will take to run, rather, it gives an idea of how an algorithm will perform when given increasingly large amounts of data. This means that for algorithms dealing with small data sets, time complexity is less important than those dealing with larger sets.

As a programmer, it is your job to decide whether or not it is worth your time to optimize a program's time complexity. If an algorithm does not have to deal with large amounts of data, it may not be wise to spend significant time rewriting it for a better time complexity.

To summarize, time complexity is a useful tool for, broadly, judging

. For general algorithms (search, sort, etc.) it is generally best to use well-known algorithms with good time complexities. For more custom algorithms, time complexity should not be a focus unless it has to deal with large sets of data or is used frequently in a program.

Library Usage

Sometimes, a situation (time constraints, metal health, etc.) forces you to make a function that may have a poor time complexity or readability. Luckily for you, computers have been around long enough for a bunch of nerds to create

full of pre-optimised functions for you to use instead.

Libraries such as <ctime>, <vector>, and <algorithm> are all full of useful, pre-built tools for you to use. Specifically, the algorithms library could help you with

and the time library with logging .

These libraries serve as a sort of tool chest for you to pull from and use. If you don't know how to write an algorithm to find the union between two sets, has you covered with it's set_union execution. The best part about these library includes is that they are ususally optimized equally or better than any solution you could come up with on your own.

Some people may be concerned that adding many libraries will slow down their program but this is not the case. The

is very good at optimizing your code for runtime and this is no different for library includes. The only increase in time usage you may experience is an increase in compliation time (which is not part of optimizing code).

Alltogether, library usage is an important concept for programmers to understand. They are a huge time save and can help you save line useage, mental energy, runtime complexity and, most importantly, time.

Overview

Optimization is a broad concept with many ideas and philosophies surrounding it. At the end of the day, they all have the same general goal: Make the code run faster and better. It is becasue of this general goal that we have focussed on time complexity and library include usage as these will have the greatest impact on new programmers. These concepts do not include all optimization techniques, however, if you are increasing the speed of your code and saving time while coding, rest assured, you are optimizing.