Will it scale?

This age-old question is always asked during the design phase of software development and comes in several flavors. From an architectural standpoint, scalability is how easy it is to make changes to your app. From a database standpoint, scalability is about how long it takes to save or retrieve data to the database.

For algorithms, scalability refers to how the algorithm performs in terms of execution time and memory usage as the input size increases.

When you’re working with a small amount of data, an expensive algorithm may still feel fast. However, as the amount of data increases, an expensive algorithm becomes crippling. So how bad can it get? Understanding how to quantify this is an important skill for you to know.

In this chapter, you’ll take a look at the Big O notation for the different levels of scalability in two dimensions--execution time and memory usage.

Time complexity

For small amounts of data, even the most expensive algorithm can seem fast due to the speed of modern hardware. However, as data increases, cost of an expensive algorithm becomes increasingly apparent. Time complexity is a measure of the time required to run an algorithm as the input size increases. In this section, you’ll go through the most common time complexities and learn how to identify them.

Constant time

A constant time algorithm is one that has the same running time regardless of the size of the input. Consider the following:

The size of the names array has no effect on the running time of this function. Whether the input has 10 items or 10 million items, this function only checks the first element of the array. Here’s a visualization of this time complexity in a plot between time versus data size:

As input data increases, the amount of time the algorithm takes does not change. For brevity, programmers use a notation known as Big O notation to represent various magnitudes of time complexity. The Big O notation for constant time is O(1).

Linear time

Consider the following snippet of code:

func printNames(names: [String]) {
  for name in names {
    print(name)
  }
}

This function prints out all the names in a String array. As the input array increases in size, the number of iterations that the for loop makes is increased by the same amount.