Back to blog

A Beginner’s Guide to Big O in Swift

---

Big O notation is a topic that can make your head spin, especially if you’re new to algorithms.

You use big O notation to describe how efficient an algorithm runs, compared to other algorithms. And we get an idea about how much more work an algorithm has to do, as the size of its input grows.

In this tutorial you’ll learn:

• What big O notation is
• Why it’s relevant for iOS/Swift developers
• What the different time complexities mean
• How you can determine the time complexity of an algorithm

What Is Big O Notation?

Imagine you’re building a music app, and your boss wants you to code an algorithm that makes music recommendations. Kinda how Amazon tells you “Products You Might Also Like”, but then for a few million music tracks across a few dozen genres.

You go to work. You build an algorithm that determines a likeness score for every music track, compared to another track. For each track you select 5 other tracks with a likeness that exceeds a certain threshold.

Once the algorithm has done its work, users of the music app would be able to see 5 similar music tracks for every track they’ve liked.

So far so good! Your algorithm works fine comparing a few of your own favourite tracks, and predicts with some certainty other tracks you might also like. Awesome!

And then you try to run those millions of songs through the algorithm…

Your computer’s CPU shoots to 400%, its memory is at max capacity, and the whole algorithm grinds to a halt. It is too much work! At this rate, it’ll take weeks for the algorithm to finish…

That’s where time complexity and big O notation come in. Big O notation is used to classify algorithms, based on how their running time grows relative to the size of the input for the algorithm.

Let’s break that down:

• Algorithms are computer programs that take input and produce output. Data goes in, the algorithm does some work, and a result comes out. Examples are sorting data alphabetically, or the recommendation algorithm described earlier.
• Classification means “to sort things in groups”. Some algorithms go in group A, because all algorithms in group A share a particular characteristic. Other algos go in group B, because they share another characteristic.

Big O notation classifies algorithms in these groups, ordered from best to worst performance:

• O(1), called constant time
• O(log n), called logaritmic time
• O(n), called linear time
• O(n2), called quadratic time

(There are more groups, but let’s not get into those today.)

Check out the graph of the above time complexities, below. You can judge by the steepness of some of the lines how quickly an algorithm’s runtime grows, as its input size grows. Ideally, we want to stay on or below the green line.

Big O notation says nothing about how much actual time, i.e. seconds, it takes for an algorithm to do its work. It says something about the time relative to the size of the input. As the input for an algorithm gets bigger, how fast does the runtime grow?

• When the input grows 2x, do we need to do twice as much work?
• When the input grows 2x, do we need to do 4x as much?
• When the input grows 2x, do we need to do the same amount of work?

With big O notation, there are two things we also talk about:

• How fast the runtime grows for arbitrarily large input sizes
• The worst case and average case scenarios for an algorithm

An example: If you’re searching an array for a particular value, you might find it at your first guess. Does this mean the algorithm is fast, or that you just got lucky?

What’s more interesting is what happens to the time it takes to run an algorithm when the size of the input gets extremely large, and what happens if we have to process all that data. That’s why we’re looking for the worst case scenario.

You can also use big O notation to express the additional space needed to run an algorithm. Just like time complexity, space complexity describes the additional space needed as the size of the input grows.

Let’s take a look at a few examples.

Constant Time With O(1)

The simplest of time complexities is constant time. An algorithm that runs in O(1) will always execute in the same time (or space) regardless of the size of the input.

Here’s an example in Swift:

let names = [“Zaphod”, “Trillian”, “Arthur”, “Marvin”, “Humma”]
let name = names[2]

The above code gets an item from an array by using an index number. It doesn’t matter if this array has 10 items or 10.000, it’ll always take the same time to get an array item by its index number. The complexity of looking up a value in an array is O(1).

Why is it so fast? The algorithm to retrieve an item from an array by index number can directly calculate the memory address of that data, based on the index. It doesn’t have to iterate or search the array – it’s a direct, instant operation.

Functions with a constant time complexity are important in software development, because O(1) algorithms execute efficiently regardless of the size of the input. Common operations like getting an item from an array by index or pushing a value onto a stack are all O(1) operations.

What’s important to point out here is that an algorithm can still be considered slow if it takes a lot of wall-time to execute. In absolute terms, one O(1) algorithm can take much more time to run than another O(1) algorithm.

But that’s not what big O notation is about! We’re talking efficiency here relative to the size of the input, not absolute performance as in “this algorithm takes 5 minutes to run.”

Linear Time With O(n)

What’s more interesting, is algorithms that execute in linear time. This means that the time the algorithm takes to complete grows linearly with the size of the input. With twice the input, we need to do twice the amount of work.

Big O notation for a linear time algorithm is O(n). The n here is the size of the input, so the size of the input is proportional to the time it takes to process that input.

If n = 100, then O(100) = 100. But we don’t actually put those numbers in, the “big O” O(n) notation is just a way to describe this time complexity class.

An O(n) algorithm that processes an array with 100 items has to do ten times as much work, compared to the same algorithm that processes an array with 10 items.

This is an algorithm in Swift that calculates the sum of an array of integers:

let numbers = [8, 5, 2, 10, 17, 2, 11]
var sum = 0

for number in numbers {
sum += number
}

print(sum)

The algorithm iterates once over every item in the array. So, as we add more numbers, the work the algorithm needs to do also grows. At what rate does it grow? At a linear rate, so its complexity is O(n).

A good example of an algorithm that runs in O(n) is finding an item in an array, whose index is unknown. In the worst case scenario, you have to check every item in the array to find what you’re looking for.

A good shorthand for determining the time complexity of an algorithm, is to count the number of n‘s, i.e. how many times you loop over the input.

Quadratic Time With O(n2)

This is where we really have to do some work. For algorithms that run in quadratic time, with O(n2), the time it takes to run them grows directly proportional to the square of the size of the input.

• For 1x input, we have to do 1x work
• For 2x input, we have to do 4x work
• For 4x input, we have to do 16x work
• For one million songs, we have to do – a sh*t ton of work!

Going back to our music recommendation app, this is where we ran into trouble. Because we’re checking every song against every other song, we’ll have to check every song again if we only add one song to the dataset! You see how that grows exponentially?

Here’s what that would look like:

for song_A in songs
{
for song_B in songs
{
let similarity = compare(song_A, song_B)
}
}

This algorithm might run OK for 25 songs, because you do 25 x 25 iterations. But imagine what happens if you add millions of songs, that’s 1.000.000 x 1.000.000 iterations. That’s a ton of work, and an algorithm with pretty poor performance.

In most scenarios, and for large data sets, algorithms with quadratic time complexities take a lot of time to execute. So, you’ll either need a lot of resources and time, or you need to come up with a better algorithm.

A good example of a O(n2) algorithm is the insertion sorting algorithm. In short, this algorithm sorts an array of items by taking items out, one by one, determining their sorted place in the output array, and putting them back in. It does so by looping over the array items once for every array item, effectively using two nested for loops. This results in a time complexity of O(n2).

Logarithmic Time With O(log n)

Algorithms with logarithmic time compexities are an odd bunch. Unlike constant, linear and quadratic time, logarithmic time is hard to grasp intuitively.

An algorithm that runs in O(log n) reduces the amount of work it needs to do as it progresses through the data set. The more work it does, the less work it still has to do. This produces a growth curve that is logarithmic. Intruiging, right?

A good example of a logarithmic time complexity is binary search. With binary search we’re looking for a certain number in a sorted array of numbers.

Here’s how it goes:

1. Start with the middle number in the array. Is it bigger or smaller than the number we’re looking for? This tells us if the number we’re looking for is left or right of that middle number.
2. Remove the part of the array the number is not in, i.e. the left or the right part. This effectively cuts the remaining work we have to do in half!
3. Go back to step one. Take the middle number, compare it with the target number, and divide in half. We’ve reduced the amount of work again!

See how the amount of work we need to do halves with every step the algorithm takes? This means that if we double the amount of data the algorithm needs to do, it’ll only take one extra step extra to cut it in half again. If you plot that on a line, you’ll get a logarithmic growth curve, or O(log n).

Why Big O Notation?

Why is it important to know about big O notation? It’s a relevant discussion for a few reasons:

• Big O notation informs how we think about efficient algorithms
• Big O notation affects what algorithms you decide to use in your work
• Big O notation is a common topic in coding interviews
• And it’s fun!

Why is big O notation useful? Because it informs the way we think about computation. A powerful, fast CPU will run an algorithm faster than a slower CPU – that’s obvious. But as our data set gets larger, an inefficient algorithm will take more and more time to run.

That’s where big O notation comes in, because it can show you how much more work an algorithm has to do as the size of the input grows. You can’t just measure that in CPU speed. You could buy more CPU power, but is that an economic choice? Big O notation helps answer that question.

Big O notation also helps you make decisions. When you’re asked to solve a problem, and you determine it can only be done in O(n2), you can decide to look for an approach with better performance. Likewise, big O notation helps you, for example, understand that quicksort performs better than insertion sort for large data sets.

Don’t just learn about big O notation because it’s part of coding interviews. That doesn’t help anyone, and you’d just forget about it once you’re hired (or not). Big O notation can help you brush up your computer science skills, because it’s a good path into learning more about algorithms and computation.

Further Reading

Big O notation can make your head spin, especially because it feels so abstract. The cool thing about O(1), O(n), O(log n) and O(n2) is that after a while, you start to see them everywhere.

Apple’s documentation for iOS and Swift often mentions the time complexity of operations. You can find out that array subscript runs in O(1) and sort(_:) uses a hybrid sorting algorithm that runs in O(n log n). And now you know exactly what that means!

Create Your App Now