Learning Big O Notation with Swift

Congratulations! As someone reading this series, you’re probably familiar with the basics of Swift/iOS Development and may be in the process of writing your next app. When building software, a question we often ask ourselves is what should be our definition of done. As an individual contributor working on a large project, features in your application may be determined by business stakeholders or a project lead. However, it takes more than requirements to build software users will love. Great systems combine detailed analysis, stellar features and performance.

As we start our journey understanding algorithms and data structures, an idea that unites each concept is the theme of Asymptotic Analysis. Often viewed as a complex topic, asymptotics is the process of describing the efficiency of algorithms as their input size grows. The notion of tracking algorithmic performance can reveal much about a solution’s effectiveness. Ironically, this area of study was primarily developed before the introduction of modern computing. Today, this provides an advantage when testing new ideas and communicating with other developers. In computer science, asymptotics is expressed in a standard format known as Big O Notation.

Linear Time

Even though we sometimes think of algorithms as complex systems, in essence, they are merely recipes for completing a series of operations. For example, a simple algorithm shared across all programming languages is a loop. In Swift, this can be written using a straightforward technique called fast enumeration. As such, we can write a simple algorithm to find a specific number in a sequence:

let sequence : Array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

//linear time - O(n)
func linearSearch(for value: Int, list: Array) -> Bool {
    
    //check all possible values
    for number in list {
        if number == value {
            return true
        }
    }
    
    return false
}
//execute search
let isFound: Bool = linearSearch(for: 8, list: sequence)

When evaluating this function we say that it works in linear time — O(n) because the effectiveness of its main action (e.g., search) is directly related to the size of its input (e.g., sequence). As a result, we can conclude that it would take longer for the function to find the value of 10 than 2 or 3. To summarize, the algorithm will have to iterate through the complete set of values when searching for a non-present value like 16. In most cases, linear time operations are referred to as being “brute force” because little effort goes into how they could run more efficiently. However, linear-based activities still provide value when prototyping complex systems in a technical interview or real-world setting.

Constant Time

When evaluating algorithms, it’s often ideal to code a solution where the size of the data input has no direct relationship on performance. Consider successful search algorithms like Google or machine learning solutions used on websites like Netflix and Amazon. These systems run in constant time and are represented with the symbol O(1). A significant difference between a linear and constant operation is logic. In the case of Google, many hardware and software complexities are put in place to ensure things work as quickly as possible. However, not all constant time operations need to be complicated. Consider the following:

 

Like this article? Get more content like this in the iOS Computer Science Lab.

 
//constant time operations - O(1)

class Stack {
    var store : [T] = []
func peek() -> T? {
        return store.last
    }
func push(_ value: T) 
        
    
func pop() -> T? {
        return store.isEmpty ? nil : store.removeLast()
    }
}

Known as a Stack data structure, this implementation is a favorite among hiring managers when conducting technical interviews. The reason? A Stack combines ideas found in native iOS Development (e.g., UINavigationController) along with specific language syntax (e.g., collections and generics) coupled with knowledge of Big O Notation. As shown, what makes a Stack useful is how it performs. For example, all actions can be executed without having to search through or analyze previously added items.

The Interview Process

Even though we’ve reviewed two specific examples, we shouldn’t think of algorithms and data structures as something to memorize to get through the technical interview process. As a developer, one can think of concepts like Big O Notation as a tool to evaluate one’s code for completeness as well as effectiveness. For example, much of Apple’s owns technical SDK documentation explains its frameworks with this commonly used terminology.

However, if you are indeed preparing for a technical interview, other regularly seen algorithmic running times include logarithmic time — O(log n), O(n log n) and O(n2). Plotted on a graph, we can see how these compare:

big-o-diagram.png