| Home | Resources | Papers | Essays | Short Fiction | About |

Algorithmic Complexity

Table of Contents

Introduction

None of the data structures or algorithms that we cover in this course exist in a vacuum. Historically, all of them have had some reason to exist for one reason or another. Practically, every algorithm also must be processed through time and with real hardware. What I mean by that is, if we run selection sort on some dataset we must send real digital signals through transistors which must be sent through more transistors and so on. All of this takes time, there is a temporal and spatial dimension to every single thing we do as computer programmers. As such, it behooves us to understand the implications of choosing one algorithm, or one data structure over another by analyzing how these abstractions perform both in theory and in practice. We will see that two algorithms solving the exact same problem can differ significatly in performance due to their different approaches.

Examples of Complexity

Before we get into some classical computer science abstractions, I would like to go through some "real world" examples that will help provide intuition on what algorithmic complexity is.

Constant Time Operations

Think about the last time you needed to flip to a particular chapter in a book. Likely the first thing you did was take a look at the table of contents and found the chapter name you were looking for. Next to the name was the page number associated with the start of the chapter. This tells you immediately where you need to open the book to get the information you needed. We would call that immediate jump to the chapter start a constant time operation. It is constant because there is no longer any need to search through pages in the book to find the chapter. The table of contents gives us the answer in a single step regardless of how long the book is.

Variable Time Operations

Let's say the book didn't come with a table of contents, most novels do not. You still want to find a particular chapter, but you don't really know where it is. The natural act is to begin scanning through the book front to back to find the chapter you're looking for. If you flip through the book one page at a time you are guaranteed to eventually find the page you are looking for, but you do not know exactly when that might happen. We would call this a variable-time operation as the time it takes to complete the task would vary with where exactly the key chapter is and how many pages the book has in the first place. Looking page-by-page, it will take longer to find the last chapter of a book than it would to find the first chapter—similarly, it will likely take longer to find a chapter in a 900 page book than a 50 page book.

Big O Notation

Many years prior to the establishment of computer science, Paul Bachmann and Edmund Landau developed a mathematical formalism for the analysis of the asymptotic behavior of functions. Bachmann-Landau notation was constructed to describe how functions "grew" at both similar and different rates. Using their notation, the formula f(n) = O(g(n)) is equivalent to saying that "f(n) grows no faster than g(n) does" such that there exists some constant value M that f(n) ≤ Mg(n). If we take f(n) to be the identity function id(n) = n and g(n) to be equivalent to square(n) = n² we could say that id = O(square). There is some constant that can be applied to square which maintains that every value of id is either equal to or less than it (in this case M could be set to 1).

As computer science tends to bend towards the practical rather than the purely theoretical, we also tend to be a bit looser with the above mathematical formalism. This comes as a direct consequence of Donald Knuth's seminal work The Art of Computer Programming where he adopted Bachmann-Landau notation for his discussions on how various algorithms and data structures can be compared in terms of both time and space complexity. We often follow his lead of dropping constant values in complexity comparisons. For example, if an algorithm has been found to be described by the formula f(n² + 2n) we would say that f(n² + 2n) = O(n²) even though that's not valid for the strict notation. This is because in computer science we are interested in how algorithms scale and the limiting scaling factor is the dominant term.

The best way to get a feel for algorithmic complexity is to see how different algorithms stack up against one another. First we'll look at two different sorting algorithms, bubble sort and merge sort, then we'll look at two different data structures, arrays and lists.

Comparing Sorting Algorithms (Bubble vs Merge Sort)

From the chapter on sorting algorithms, we're already familiar with bubble sort. Bubble sort has us "floating" larger values "up" to the end of an array. Merge sort is an entirely different beast. It is a recursive algorithm which works by progressively splitting an array in two and sorting each smaller array within each split. I've provided a Java implementation of both below: 

 1: public class BubbleSort{
 2:     public static void swap(int a, int b, int[] arr){
 3:         int temp = arr[a];
 4:         arr[a] = arr[b];
 5:         arr[b] = temp;
 6:     }
 7:     public static void sort(int[] arr){
 8:         boolean swapped = false;
 9:         int j = arr.length;
10:         do{
11:             swapped = false;
12:             for(int i = 1; i < j; i++){
13:                 if(arr[i-1] > arr[i]){
14:                     swap(i-1, i, arr);
15:                     swapped = true;
16:                 }
17:             }
18:             j--;
19:         } while(swapped == true);
20:     }
21: }

 1: public class MergeSort{
 2:     public static void mergesortMerge(int[]b, int begin, int middle, int end, int[] a){
 3:         int i = begin;
 4:         int j = middle;
 5:         for(int k = begin; k < end; k++){
 6:             if(i < middle && (j >= end || a[i] <= a[j])){
 7:                 b[k] = a[i];
 8:                 i += 1;
 9:             }else{
10:                 b[k] = a[j];
11:                 j += 1;
12:             }
13:         }
14:     }    
15:     public static void mergesortSplit(int[] b, int begin, int end, int[] a){
16:         if((end - begin) <= 1){
17:             return; // size == 1 -> sorted
18:         }
19:         int middle = (end + begin) / 2;
20: 
21:         mergesortSplit(a, begin, middle, b); //left half
22:         mergesortSplit(a, middle, end, b); //right half
23: 
24:         mergesortMerge(b, begin, middle, end, a);
25:     }    
26:     public static void mergesort(int[]a, int[]b){
27:         for(int i = 0; i < a.length; i++){
28:             b[i] = a[i];
29:         }
30:         mergesortSplit(a, 0, a.length, b);
31:     }    
32:     public static void sort(int[] arr){
33:         mergesort(arr, new int[arr.length]);
34:     }
35: }

You are not expected to memorize the merge sort algorithm.

I have also provided a program to test these implementations: 

 1: import java.io.*;
 2: import java.util.Arrays;
 3: public class BigO{
 4:     public static class InvalidSort extends RuntimeException{
 5:         InvalidSort(String msg){
 6:             super(msg);
 7:         }
 8:     };    
 9:     public static int[] loadValues(String filename){
10:         int[] arr = null;
11:         try (BufferedReader buffer = new BufferedReader(new FileReader(filename))) {
12:             int size = Integer.parseInt(buffer.readLine());
13:             arr = new int[size];
14:             String num;
15:             int i = 0;
16:             while ((num = buffer.readLine()) != null){
17:                 arr[i] = Integer.parseInt(num);
18:                 i += 1;
19:             }
20:         }catch(Exception e){
21:             System.err.println(e);
22:         }
23:         return arr;
24:     }
25:     public static void printArr(int[] arr){
26:         System.out.print("[");
27:         for(int e : arr){
28:             System.out.print(e + ",");
29:         }
30:         System.out.println("]");
31:     }    
32:     public static void main(String[] args){
33:         int[] arr = loadValues(args[0]);
34:         String sortChoice = args[1];
35:         Runtime runtime = Runtime.getRuntime();
36:         System.gc();
37:         long beforeUsedMem=runtime.totalMemory()-runtime.freeMemory();
38:         long start = System.nanoTime();
39:         if(sortChoice.equals("bubble")){
40:             BubbleSort.sort(arr);
41:         }else if(sortChoice.equals("merge")){
42:             MergeSort.sort(arr);
43:         }else{
44:             throw new InvalidSort("No Valid Sort Found!");
45:         }
46:         long end = System.nanoTime();
47:         System.gc();
48:         long afterUsedMem=runtime.totalMemory()-runtime.freeMemory();
49:         double seconds = (end-start) / (1000000000.0);
50:         long actualMemUsed=afterUsedMem-beforeUsedMem;
51:         System.out.println(String.format("Execution time: %.2fs", seconds));
52:         System.out.println(String.format("Memory Used: %d", actualMemUsed));
53:     }
54: }

Here is a python script that can generate the input used by this program: 

1: import random
2: import sys
3: numInts = int(sys.argv[2])
4: with open(sys.argv[1], "w") as fp:
5:     fp.write(f"{numInts}\n");
6:     for i in range(numInts):
7:         fp.write(f"{random.randint(0, 1000)}\n");

We can then run BigO on both algorithms with 100 integers: 

josephraskind@stargazer:/tmp/bigO/bigO$ java BigO.java input/100.txt bubble
Execution time: 0.04s
Memory Used: -560
josephraskind@stargazer:/tmp/bigO/bigO$ java BigO.java input/100.txt merge
Execution time: 0.07s
Memory Used: -744

There's not a lot of difference between the two. Let's try 100,000 integers: 

josephraskind@stargazer:/tmp/bigO/bigO$ java BigO.java input/100000.txt bubble
Execution time: 16.99s
Memory Used: 1392
josephraskind@stargazer:/tmp/bigO/bigO$ java BigO.java input/100000.txt merge
Execution time: 0.07s
Memory Used: 1688

We see that merge sort has massive speedup when compared to bubble sort. This has to do with the fact that merge sort's recursive algorithm breaks the sorting problem down into smaller parts that are all looked at independently of each other prior to being merged. Bubble sort has no choice but to look at the entire array of values every loop! We say that bubble sort has O(n²) whereas merge sort has O(nlogn).

When speaking, we say that bubble sort has a "big O of n squared".

Something that is not as obvious, as the way of getting memory usage during the Java execution is a bit crude, is that the merge sort gains are not without consequences. Merge sort takes up way more memory than bubble sort does. Every algorithm has both time and space tradeoffs. Beyond that, it's clear that it's also much harder to write merge sort than it is to write bubble sort. What we gain in speed we lose in implementation complexity.

Comparing Data Structures (Arrays vs Linked Lists)

Now let's compare the complexity of two classic data structures: arrays and linked lists. If we take a look at insertion between arrays and linked lists it's clear that the winner would have to be linked lists. Linked lists can add elements in constant time whereas arrays must be recreated and old elements must be copied over before another element can be added in. However, arrays have the advantage of constant time access that linked lists don't. It is impossible to search through a linked list any faster than looking at each element one at a time; however, it is possible to write a search algorithm for a linked list that can make use of constant time access (we'll soon learn about the binary search algorithm).

I leave it as an exercise for the reader to benchmark these realities on their own.

Exercises

  1. The chapter introduces Big O notation as a way to describe how algorithms scale. For each of the following operations, identify the Big O complexity and justify your answer using the real-world analogies from the chapter:
    • Retrieving an element from a Vector<T> by index
    • Searching for an element in an unsorted LinkedList
    • Bubble sort on an array of n elements
    • Appending to a LinkedList<T> that has a tail pointer
    • Finding the minimum element in an unsorted array
  2. The chapter shows that f(n² + 2n) = O(n²) because the dominant term is n². Simplify each of the following to its Big O class and explain which term dominates and why:
    • f(5n³ + 100n² + n)
    • f(n + log n)
    • f(2ⁿ + n¹⁰⁰)
    • f(n log n + n²)
    • f(1000)
  3. Compile and run BigO.java with both bubble sort and merge sort on a small input (10 elements), a medium input (5,000 elements), and a large input (100,000 elements). Record the execution time for each combination. Does the execution time scale as you would expect from the Big O class of each algorithm? At what input size does the difference between the two algorithms become clearly visible?
  4. The chapter motivates algorithmic complexity through the observation that all computation takes real time on real hardware. Consider two algorithms: one that runs in O(n²) and one that runs in O(n log n). For small inputs the O(n²) algorithm might actually be faster due to lower constant overhead. Design an experiment using BigO.java that finds the crossover point—the input size at which merge sort becomes faster than bubble sort on your machine. What does this tell you about the relationship between theoretical complexity and practical performance?

Previous | Index | Next

Contact: [email protected] | rss feed | Compiled with org-mode | Licensed under CC BY-NC-SA 4.0