June 15th, 2015

- Zed Shaw

Teaching Big-O to programming students, you lose the majority of them the minute you show them static graphs. The Lost only seem to make it back years later when they’re working full-time and they have to resolve real bottlenecks - some of which could’ve been prevented had they not mentally left the room minutes into their time-complexity lectures.

After Craig Federighi introduced playgrounds at WWDC 2014, I judiciously took skeptical notes - would they accelerate development at the expense of good design? Would they stain the huge object graphs we've carefully 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 and took instruction from the kids’ unequivocal verdict.

As for getting things done, students want simple. KISS and DRY principles are repeated while languages are championed for their simple syntax. And, as students, it's often either low hanging fruit, or no fruit at all.

Witness 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(var arr:Array<Int>) -> Array<Int>{
var x, y, z, passes, key:Int
for x in 0..<arr.count{
passes = (arr.count - 1) - x
for y in 0..<passes{
key = arr[y]
if (key > arr[y+1]){
z = arr[y+1]
arr[y+1] = key
arr[y] = z
}
}
}
return arr
}
// O(n log(n)), (worst case and average case)
func mergeSort(var 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(leftArray), mergeSort(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 bubbleSort(bubbleArray) and mergeSort(mergeArray) to get things rolling.

```
for (var i = 0; i < twoDimensionalArray.count; i++){
var bubbleArray = twoDimensionalArray[i] as Array
```
let bubbleStart = NSDate().timeIntervalSince1970
bubbleSort(bubbleArray)
let bubbleEnd = NSDate().timeIntervalSince1970
let bubleExecution = bubbleEnd - bubbleStart
var mergeArray = twoDimensionalArray[i] as Array
let mergeStart = NSDate().timeIntervalSince1970
mergeSort(mergeArray)
let mergeEnd = NSDate().timeIntervalSince1970
let mergeExecution = mergeEnd - mergeStart
}

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 be able to *experience* bubble sort take exponentially longer to run as the 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.

Students wait, and wait some more as bubble sort's results panel begins to resemble a gas station pump as you fill up an empty tank, while merge sort resembles more a slot machine - its time logarithmically increasing despite a ballooning input.

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 vs binary search

Sorting and searching go together like fishing and beer. And from a teacher's POV, brute force search shows that "complexity", in this context, does not mean the number of things an algorithm does. Watching this playground with brute force search struggle to find 79,999 in an array 80,000 elements should clear this up for your students - especially if it crashes the Mac. Just make sure you reiterate that this is the worst case.

```
func bruteForceSearch(key:Int, arr:Array<Int>){
if (arr.last! == key){
println("value \(key) found")
return
}
for i in arr{
if i == key{
println("value \(key) found")
return
}
}
println("key \(key) not found")
}
```

Binary search from the playground

```
func binarySearch(key:Int, minInt:Int, maxInt:Int, var arr:Array<Int>){
if (maxInt == key){
println("value \(key) found")
return
}
var midIndex:Double = round(Double((minInt + maxInt)/2))
var midNumber = arr[Int(midIndex)]
if (midNumber > key){
binarySearch(key, minInt, Int(midIndex) - 1, arr)
}else if (midNumber < key){
binarySearch(key, Int(midIndex)+1, maxInt, arr)
}else if (midNumber == key){
println("value \(key) found")
}else{
println("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 last element in 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.

Finalmente

As playgrounds evolve, I hope that we’ll be able to reduce the time field’s parameter to less than one second. Also, I hope to be able to precompile collections as it takes much longer to populate our arrays than to sort or search them (the resources folder doesn't allow top-level code execution).

*Bonuses

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–2015 Mike Leveton