Introducing big-O notation

Big-O notation is a way to describe running time, or how long an operation takes to complete. The idea is that the exact time an operation takes isn’t important; it’s the relative difference in scale that matters.

Imagine you have a list of names in some random order, and you have to look up the first name on the list. It doesn’t matter whether the list has a single name or a million names — glancing at the very first name always takes the same amount of time. That’s an example of a constant time operation, or O(1) in big-O notation.

Swift Apprentice Section II: Collection Types

Now say you have to find a particular name on the list. You need to scan through the list and look at every single name until you either find a match or reach the end. Again, we’re not concerned with the exact amount of time this takes, just the relative time compared to other operations.

To figure out the running time, think in terms of units of work. You need to look at every name, so consider there to be one “unit” of work per name. If you had 100 names, that’s 100 units of work. What if you double the number of names to 200? How does that change the amount of work? The answer is it also doubles the amount of work. Similarly, if you quadruple the number of names, that quadruples the amount of work.

This is an example of a linear time operation, or O(N) in big-O notation. The size of the input is the variable N, which means the amount of time the operation takes is also N. There’s a direct, linear relationship between the input size (the number of names in the list) and the time it will take to search for one name.

You can see why constant time operations have the number 1 in O(1). They’re just a single unit of work, no matter what!

You can read more about big-O notation by searching the Web. You’ll only need constant time and linear time in this book, but there are other such time complexities out there.

Big-O notation is particularly important when dealing with collection types, because collections can store very large amounts of data, and you need to be aware of running times when you add, delete or edit values.

For example, if collection type A has constant-time searching and collection type B has linear-time searching, which you choose to use will depend on how much searching you’re planning to do.

Arrays are the most common collection type you’ll run into in Swift. Arrays are typed, as are regular variables and constants and store multiple values like a simple list.

Before you create your first array, let’s take some time to consider in detail what an array is and why you might want to use one.