June 15th, 2015

Updated for Swift 4

- Zed Shaw

Teaching Big-O to programming students, you lose the majority of them the minute you show them static graphs. They propably won't remember the graphs two years later when they're puzzling over bottlenecks as full-time developers. Our hope is that their takeaway that fateful day is that time complexity is not just academic.

I was skeptical when Craig Federighi introduced playgrounds at WWDC 2014 - would they accelerate development at the expense of good design? Would we lose touch with the huge object graphs we'd built class-by-class? Then months later I observed a group of teenagers playing with Apple's Mandelbrot playground - They went wild with delight. Abruptly feeling absurd, I deleted my notes of skepticism and took instruction from the kids’ unequivocal verdict.

As for getting things done, students want simple. KISS and DRY principles are repeated and languages like Python are taught over C for their simple syntax. For many students, who could grow slowly into good developers, it's either low hanging fruit or they go hungry.

Watch bubble sort, how nice does it look compared to merge sort? It's up to us to show that sometimes you have to add a little complexity to reduce complexity.

```
// O(n^2), (worst and average case)
func bubbleSort(array:Array<Int>) -> Array<Int>{
var mutableArray = array
var next:Int, passes:Int, key:Int
//Nested loop - n^2
for x in 0..<mutableArray.count{
passes = (mutableArray.count - 1) - x
for y in 0..<passes{
key = mutableArray[y]
if (key > mutableArray[y+1]){
next = mutableArray[y+1]
mutableArray[y+1] = key
mutableArray[y] = next
}
}
}
return mutableArray
}
// O(n log(n)), (worst case and average case)
func mergeSort(unsortedArray:Array<Int>)->Array<Int>{
if unsortedArray.count < 2 {
return unsortedArray
}
let pivot:Int = unsortedArray.count/2
let leftArray:Array<Int> = Array(unsortedArray[0..<pivot])
let rightArray:Array<Int> = Array(unsortedArray[pivot..<unsortedArray.count])
return merge(mergeSort(unsortedArray: leftArray), mergeSort(unsortedArray: rightArray))
}
...
```

Just don't repeat that last part verbatim because you'll confuse them even more. Instead, create a playground with both sorting functions and let them play with the loop's input while playgrounds does the rest.

Since the playground plots every declared variable in a loop, we can loop through a two-dimensional array of unsorted arrays to see a graph of the execution time for each run (warning: this playground takes several minutes to run, so have something to read while your students suffer its horrible time profile).

Open the playground and uncomment sortedArray = bubbleSort(array: bubbleArray) and sortedArray = mergeSort(unsortedArray: mergeArray) to get things rolling.

```
for i in 0..<twoDimensionalArray.count{
var sortedArray:Array<Int> = []
let bubbleArray = twoDimensionalArray[i] as Array<Int>
let bubbleStart = NSDate().timeIntervalSince1970
sortedArray = bubbleSort(array: bubbleArray)
let bubbleEnd = NSDate().timeIntervalSince1970
let bubbleExecution = bubbleEnd - bubbleStart
print("bubble sort took \(bubbleExecution) seconds")
let mergeArray = twoDimensionalArray[i] as Array<Int>
let mergeStart = NSDate().timeIntervalSince1970
sortedArray = mergeSort(unsortedArray: mergeArray)
let mergeEnd = NSDate().timeIntervalSince1970
let mergeExecution = mergeEnd - mergeStart
print("merge sort took \(mergeExecution) seconds")
}
```

With its results sidebar, a playground will show the number of times an algorithm is recursively executed and the number of times a loop or comparison is run. For long-running routines like bubbleSort(), students will not only see how much quicker it is to merge than to bubble, they'll also be able to *experience* bubble sort take exponentially longer to run as its input increases.

The results sidebar iterates each time a function is recursed, so calling merge sort and bubble sort one after the other allows students to see easily see, in real time, how hard the two are working.

Bubble sort's results panel begins to resemble a broken gas station pump meter and because they've already put their credit card in, students must wait and suffer. Merge sort resembles all the station's other working pumps, speeding along, allowing whole caravans to get needed fuel for their beach trips - its time logarithmically increasing despite the ballooning input for 6,000 lb SUV's.

Results panel for bubble sort - comparing, swapping and spinning away

Students can recognize all this without being good at math.

Even better, you can declare variables to store the the amount of time each run takes to execute, and playgrounds will plot the times for you.

For each run, assign a variable to the difference between when the function was called and when it returned:

Results views for bubble and merge sort after four arrays were sorted

Because the x-axis is relative to the total amount of time it took to sort all the collections, ignore the slope of the graph and pay attention to the differences between each point.

Brute force search vs binary search

Graphs will lose some kids and semantics will confuse the one's who are left. Students map "complexity" to the number of things an algorithm does. Watching this playground, with a simple brute force search implementation, struggle to find integer 79,999 in an array of 80,000 elements should clear this up - especially if it crashes the Mac. Just make sure you reiterate that this is worst case.

```
func bruteForceSearch(_ key:Int, _ array:Array<Int>){
guard let last = array.last else {
return
}
if (last == key){
println("key \(key) found as last")
return
}
for i in array{
if i == key{
print("key \(key) found")
return
}
}
print("key \(key) not found")
}
```

Binary search

```
func binarySearch(_ key:Int, _ minInt:Int, _ maxInt:Int, _ array:Array<Int>){
if (maxInt == key){
print("key \(key) found as last")
return
}
let midIndex:Double = round(Double((minInt + maxInt)/2))
let midNumber = array[Int(midIndex)]
if (midNumber > key){
binarySearch(key, minInt, Int(midIndex) - 1, array)
}else if (midNumber < key){
binarySearch(key, Int(midIndex)+1, maxInt, array)
}else if (midNumber == key){
print("key \(key) found as mid number")
}else{
print("key not found")
}
}
```

Like the sorting playground, the two are run in a loop with a two-dimensional array. This time the arrays are sorted and the worst case (the count of the array minus one for brute force) is the default. Just like Sorting.playground, uncomment bruteForceSearch(secondToLastElement, array) and binarySearch(secondToLastElement, array[0], last, array) to get things rolling.

Results views for bubble and binary search after the last elements were found in six arrays

That bruteForceSearch's run time is growing at a faster clip than binarySearch's can be seen. But this could've been modeled with a simple Xcode project. Playgrounds provide a richer way for students to feel the slowness.

- - For a 1,000 element list, brute takes 0.398 seconds, binary takes 0.017 seconds.
- - For a 5,000 element list, brute takes 1.706 seconds, binary takes 0.011 seconds.
- - For a 10,000 element list, brute takes 2.913 seconds, binary takes 0.013 seconds.
- - For a 20,000 element list, brute takes 6.312 seconds, binary takes 0.014 seconds.
- - For a 40,000 element list, brute takes 15.508 seconds, binary takes 0.017 seconds.
- - For a 80,000 element list, brute takes 26.864 seconds, binary takes 0.015 seconds.

Bonus

Value semantics are also demo'd in the playground - arrays assigned to other arrays are copied, allowing for faster population.
You can also show the playground engine’s cache at work by running this script a few times and noting how the time differentials dramatically decrease.

Both playgrounds are here:

Copyright © 2011–2018 Mike Leveton