I needed an original Big-O chart for a publication. This tutorial does not cover what Big-O actually is, just how to chart it. If you want more information on Big-O I recommend reading this and this. I know, go figure, for a computer science student. I really like using R for all things chart and visualization. So, I turned to R for this task. While this is a very simple chart, it does demonstrate several very common tasks in R:

  • Overlaying several plots
  • Adding a legend to a plot
  • Using “math symbols” inside of the text on a chart
  • Stripping off all the extra whitespace that R likes to generate

You can see the end-result here:

Computer Science Big-O Chart in R

This was produced with the following R code:

# Remove white space on chart
par(mar=c(4,4,1,1)+0.1)

# The x & y limits for the plot
xl <- c(0,100)
yl <- c(0,1000)

# Just use R's standard list of colors for the lines (I am too tired to be creative this morning)
pal <- palette()

# Plot each of the equations that we are interested in. Note the add=TRUE
# it causes them to overlay each other.
plot(function(n) (rep(1,length(n))),xlim=xl,ylim=yl,col=pal[1],xlab="Elements(N)",ylab="Operations")
plot(function(n) (log(n)),xlim=xl,ylim=yl,col=pal[2],add=TRUE)
plot(function(n) (n),xlim=xl,ylim=yl,col=pal[3],add=TRUE)
plot(function(n) (n*log(n)),xlim=xl,ylim=yl,col=pal[4],add=TRUE)
plot(function(n) (n^2),xlim=xl,ylim=yl,col=pal[5],add=TRUE)
plot(function(n) (2^n),xlim=xl,ylim=yl,col=pal[6],add=TRUE)
plot(function(n) (factorial(n)),xlim=xl,ylim=yl,col=pal[7],add=TRUE)

# Generate the legend, note the use of expression to handle n to the power of 2.
legend('topright', c("O(1)","O(log(n))","O(n)","O(n log(n))",
 expression(O(n^2)),expression(O(2^n),"O(!n)"))
 ,lty=1, col=pal, bty='n', cex=.75)