Chapter 8. Performance and Algorithm Efficiency

In this chapter, we are going to see algorithms in terms of performance and efficiency. We have been implementing different algorithms in previous chapters, and now we are going to explain how we can measure them, in theory and in practice. We are going to use the help of asymptotic analysis and Big-O notation to classify and compare algorithms.

The topics covered are as follows:

• Algorithm efficiency

• Measuring efficiency

• Big-O notation

• Orders of common functions

• Evaluating runtime complexity

Algorithm efficiency

When we need to use an algorithm to solve a problem, the first question is, which algorithm is the best to solve this particular problem? Usually, we can have multiple alternatives that will solve our problem, but we need to choose the best one.

Here is where algorithm efficiency can help us decide which one is a better fit. The efficiency of an algorithm is divided into two main categories:

• Space analysis: Algorithms use different data structures and temporal variables to achieve their goal. We have seen how sort algorithms and others use structures such as arrays, stacks, queues, trees, sets, and so on. So when memory space is a constraint, space analysis is a critical criterion to check. This requirement was very important in the past, when memory was a big constraint, but it should not be overlooked now. For example, RAM memory in mobile applications is very important.

• Time analysis: Some algorithms are faster than others. Some algorithms are fast when the input data...

Measuring efficiency and the Big-O notation

Any algorithm is going to have its own running time and space complexity. As we have seen, these two variables are not fixed, and usually they depend on the input data. We have also seen that we can have a high level idea with the best, worst, and average complexities. In order to express them in an easy way, we are going to use asymptotic analysis and the Big-O notation.

Asymptotic analysis

Asymptotic analysis gives us the vocabulary and the common base to measure and compare an algorithm's efficiency and properties. It is widely used among developers to describe the running time and complexity of an algorithm.

Asymptotic analysis helps you to have a high-level picture of how an algorithm behaves in terms of memory and speed depending on the amount of data to process. Look at the following example.

Imagine a very simple algorithm that just prints the numbers of an array one by one:

let array = [1,2,3,4,5] 
for number in array { 
    print...

Orders of common functions

When we compare the Big-O of two algorithms, we are comparing at the end how the running time and space requirements grow depending on the input data. We need to know how the algorithm will behave with any amount of data. Let's see the orders of common functions in ascending order.

O(1)

When the running time is constant, always with the same value, we have O(1). So the algorithm space/running time is not dependent on the input data. One example is the time needed to access an item in an array with the index. It uses just one instruction (at a high level) to do it. The pop function on a stack is another example of O(1) operations. The space complexity of the insertion sort also uses just one memory register, so it is O(1).

Here is an example:

    public func firstElement(array:[Int]) -> Int? 
    {
        return array.first
    }

Here we have a very simplified function that receives an array of integers and returns the first one (if it exists...

Evaluating runtime complexity

Now that you have the big picture in mind, let's look at some real data for the time performance of common Big-O functions so you will definitely understand the magnitude of the different orders. These running times are done in a faster computer where a simple instruction takes just one nanosecond. Take a look at the following table:

Big-O types and performance – running times for different inputs

The grayed section is colored because the times are not practical in real-world applications. Any algorithm with a running time of more than 1 second is going to have an impact in your application. So by looking at the data provided by this table, some conclusions arise:

• For a very tiny n (n < 10), almost any order function works quick

• Algorithms that run on log(n) can have a huge amount of data without becoming slow at all

• Linear and n*log(n) algorithms have a great performance for huge inputs

• Quadratic functions (n²) start to have bad performance for n>10,000

• Algorithms...

Summary

In this chapter, we've learned about algorithm efficiency and how to measure it. We now know about Big-O notation and the syntax used to describe how an algorithm behaves in time and space for any input data size. We have a clear picture of the different Big-O order functions and we can identify the order of different pieces of code. We have also seen how to measure any method in Swift using different functions. In the next chapter, we are going to put into practice what we know about algorithms in order to select the appropriate one for different scenarios.