In the previous article, 'Introduction to algorithms', we brushed over the definition of algorithms, algorithmic thinking and the measure of the efficiency of algorithms. In this article, we'll go a little more into the efficiency of algorithms, starting with the concept of Big O notation.

If you're new to this series and interested in learning and following along, you might want to start with this article. This series consists of concepts from FreeCodeCamp's tutorial Algorithms and Data Structures Tutorial - Full Course for Beginners, go ahead and check it out to grasp as much as you can.

Contents

• What is Big O?
• Time and Space Complexity
• Common Complexities
• Conclusion

Big O Notation

Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given a problem size n, where n is usually the number of items in our input. Another theoretical definition of Big O would be to describe it as the complexity of an algorithm as a function of the size - meaning Big O measures time complexity as the input size grows.

Its notation is O(n) meaning the Order of magnitude of complexity, and it is read as Big O of n.

Understanding why Big O is such an important concept is a major advantage. It's useful for understanding the time and space complexities of varying algorithms. However, it's useful only when comparing algorithms that solve the same problem because it helps you decide which is the most optimal for the solution you want to implement.

Big O alone isn't a great measure for efficiency. There are other factors that may affect the efficiency of the algorithm as well, such as the operating system or the type of programming language you're using.

It is also described as the upper bound of the algorithm and what that means is that it measures an algorithm's performance based on its worst-case scenario.

Time and Space Complexity

The math behind time and space complexities is important if we're designing and analyzing an algorithm, but our goal in this series is to understand and evaluate them.

In this previous article, we described time complexity as the time taken by an algorithm to solve a problem. It is much more clear than describing it as the measure of how long it takes an algorithm to run. It is always measured in the worst-case scenario for better accuracy.

Consider the definition: Big O is a measure of complexity as a function of size. Let's say we want our algorithm to print "hello world", n number of times - n is the size of our input. The time taken to execute our algorithm is n, because we're printing "hello world" n times. As n increases the amount of time taken to print "hello world" also increases linearly. This means time taken to execute our algorithm(the run time) is directly proportional to the size of the input, and our algorithm is said to run on linear time - O(n).

The execution of time of an algorithm is affected by the operating system, programming language, and even the processors in your computer.

With space complexity, we only measure how much storage is needed as an algorithm grows. It's good to keep in mind if you wish to make your solution as efficient as possible. Similar to time complexity, it is always measured in it's worst-case.

Algorithms such as linear search or binary search do not increase in size as the algorithm grows. For example when searching through a list, since we only look through sections of our list by redefining the indexes, the space required to store the list same is the same throughout execution. This then means that these algorithms take up a constant amount of space - O(1).

Common complexities

Now let's discuss the notation of run time complexities, what does it mean when an algorithm takes O(1) or O(n) time? These are all Big O notations for the runtime complexities of our algorithms and we'll discuss the common runtimes that you're most likely to come across while learning about Big O.

Constant time O(1)

An algorithm is said to run on constant time when the time it takes to execute is independent of the size of the input. For example, accessing a value from a list using an index value = my_array[0]. It doesn't matter how big the list is, you're just accessing one value. It's similar to declaring a variable. However, if we were searching through the list for a index that would be a different story, consider the next example.

Linear time O(n)

Let's say we have a target value 'e' that we want to find in a list. If we use a for loop to search each index until we find our target and it turns out that it is the last item in the list (this is the worst-case) we would have to iterate through each item in the list until we got to 'e'. For an array of size n, it means we have an input of size of exactly n elements, and we would search the list exactly n times to find our target.

The time taken to search the list is linearly proportional to the size of the list.

Sound familiar? It's linear time O(n)

Logarithmic time O(log n)

With logarithmic runtimes, the number of operations decreases as the size of our input increases. A good example of this is the binary search algorithm. Using binary search we can reduce the number of search operations by half for each iteration and the efficiency of this algorithm becomes really significant if you think of searching through a list of 1 million names. In the worst-case scenario, your list would be the last item in the list, if you used linear search to have exactly 1 million search operations to find the name. However, with binary search, you'd halve the list by 2 in each iteration until you got to the name, reducing the number of operations to about 20 - that's impressive.

To explain it in logarithmic notation: We have to perform about 20 halving operations to get to our million

2^20 =1048576

Let's say N = 1048576, the size of our input.

2^20 = N

Using logarithmic notation, we know

Log2N = 20

Here's where we derive log n.

For each iteration, we reduce our input by n/2 and as result reduce the number of search operations we have to perform. This halving operation is what results in logarithmic time. We will explore it more in future algorithms.

Conclusion

I hope you enjoyed the article, after reading this you should know what Big O notation is, what it's used for, as well as some of the common runtime complexities popular with Big O. More of these runtimes will be discussed in the future, but I hope this served you well. In the next article, we'll discuss a few more runtimes and get started on recursion.