Measuring Efficiency

In the previous demo, you implemented a solution that loops through all the numbers between the two inputs and creates a sum for them.

In this part, you’ll learn how to assess a solution’s efficiency even before you implement it. You’ll learn how to measure it and understand the basics of Algorithm Complexity.

Use the code you wrote as a reference:

var sum = 0
for i in minValue...maxValue {
  sum += i
}
return sum

With the inputs one and 10, you perform 10 steps to calculate the sum. With one and a thousand, it’s a thousand steps.

Algorithms that have a linear growth to the input given to them have their complexity measured by the Big O notation O(n), where n is the input size.

The Big O notation helps you understand the algorithm’s performance. Some have a linear increase, others have an exponential increase, and some have no increase at all and are measured as O(1).

The larger the n in Big O notation, the slower the algorithm is.

An example for O(n^2) (n to the power of 2) would be a nested loop with both outer and inner iterating from 1 to n:

for outerIndex in 1...n {
  for innerIndex in 1...n {
    doSomething()
  }
}

For every pass through the outer loop, there are n passes through the inner loop. That’s going to be a lot of looping.

Although modern computers are very fast — even mobile phones now have faster processors than what computers had a decade ago — that doesn’t mean you shouldn’t care about optimizing algorithms. You should always do your best to reach the solution in the fewest steps. That’s why there are tens of algorithms for sorting, each with their pros and cons. Some algorithms take more memory than others to reach the solution.

In the next demo, you’ll measure how much time your computer takes to execute the code you implemented in the previous demo. You’ll see how much time is needed for different inputs and if there’s a better way to reach the same solution with fewer steps.