Practical Big-O, Part I

What does big-O mean exactly? Stop. Think about it. Chances are high that you will be asked to classify an algorithm’s asymptotic time complexity at some point in your career as a software developer, either in a technical interview or by a colleague. This series of articles will provide you with all of the context, theory and examples necessary to be able to answer the aforementioned question precisely and talk about big-O intelligently. The first two parts in this three part series will focus on applying big-O generally. The third part will focus on determining the big-O of a recursive algorithm.

Big-O notation is borrowed from mathematics. A branch of computer science called computational complexity theory borrows this notation in order to classify how costly a problem is to solve. Computational complexity theory is concerned with classifying problems based on the resources needed to solve a problem programmatically (i.e., solve a problem using an algorithm). We typically think of resources in terms of time (How much time does this algorithm take to run?) - but resources can be anything an algorithm needs to run, like computer memory or network bandwidth.

A Rigorous Definition of Big-O

We use big-O notation to state the worst-case asymptotic time complexity of an algorithm. When determining the asymptotic time complexity of an algorithm we are only concerned how the running time of an algorithm changes for very large input sizes.

Practically speaking, determining how an algorithm’s running time scales with large input sizes (i.e., scales asymptotically) makes sense. Most modern computers can run even the most inefficient algorithms in milliseconds so performance doesn’t matter in the small input size regime. Only when an algorithm begins to process larger input sizes does the efficiency of that algorithm become important.

Now I want to begin clearing up what I mean by running time - in doing so other related concepts will become clear. Running time is simply the total amount of time an algorithm takes to run. What the algorithm is doing during the time it runs can be thought of as being broken up into a series of constant time operations. What is an operation? An operation is any primitive computation that we assume a computer’s CPU can do in a roughly fixed amount of time. For example in the average function below we assume that adding to sum is a single, constant-time basic operation and that dividing sum by array.length is equal to 2 basic operations.

function average(array) {  
  var sum=0;
  for (var index=0; index<array.length; index++) {
    sum = sum + array[index];
  }
  return sum/array.length;
};

Running time is proportional to the number of operations needed to complete an algorithm. If we consider an algorithm as a sum of steps, or operations, each taking a constant number of time we can then define a general equation for the running time of an algorithm. This equation represents the number of operations an algorithm needs to take - with respect to input size - in order to complete. For average we get,

T(n) = n + 2.

Each iteration of the for-loop takes a constant amount of time for each input. The step where sum is divided by array.length occurs precisely once.

Now we have translated average into a function, namely T(n). If we were to
graphically represent T(n) we would plot n on the x-axis and T(n) on the y-axis. This plot would look roughly linear.

Procuring an equation like T(n) can be done for any algorithm.

Now let’s formally define big-O:

Definition: T(n) = O(f(n)) if and only if there exists constants c, n0 > 0 such that T(n) is less than or equal to the product of some constant c and f(n), for all n greater than n0.

What this means is that at some input size n0 we can define a function f(n) that will always be greater than or equal to T(n) divided by some constant for all input larger than n0. Looking at average we could define a constant c = 2 and let f(n) = n, which corresponds to O(n). This would then give us n0 = 2. In other words,

T(n) = n + 2 is less than or equal to 2n for all n greater than or equal to 2.

Since f(n) = n then we say, by definition, that average has a worst-case time complexity of O(n). Intuitively what this is saying is that beyond some point n0, T(n) grows as fast or more slowly than f(n) times c. The graph above is demonstrating that. As you can see at n0 T(n) is less than f(n) times c for all values of n greater than n0.

Now let’s talk about what inputs big-O requires. Big-O yields the worst-case asymptotic time complexity of an algorithm. Let’s say we have a sorting algorithm like bubblesortCheck (see below). bubblesortCheck cycles through an array of length n, n number of times, swapping any two consecutive integers in which a bigger integer precedes a smaller integer. Let's say it also has some constant time method called arrayIsSorted that checks to see if the array is already sorted at each iteration. If the array is already sorted bubblesortCheck terminates on the first iteration of the loop and returns the sorted array. Here is bubblesortCheck in pseudocode.

function bubblesortCheck(array)  
  for each index in the array
    for each index in the array
      if arrayIsSorted is true
         return array
      else
        swap any two unsorted consecutive integers
  return sorted array

If you were to pass an already sorted array into this algorithm, bubblesortCheck would sort in constant time, instead of O(n2). An already sorted array is the best case input for this algorithm. The worst case input would be one that takes bubblesortCheck the maximum amount of time (and requires the most operations) to run: this would be a reversed array. Each algorithm has a best and worst case input.

Big-O notation is only concerned with the worst-case input. It is an upper-bound on the running time of an algorithm.


Interested in learning more about JavaScript? Visit us at http://www.makersquare.com/.