AWK program to compare time complexity of joining strings

join.awk

# AWK program to compare time complexity of joining strings using a
# simple O(N^2) algorithm and a slightly more complex O(N log N) one.

# Join array elements, separated by sep: O(N^2) version
function join1(a, sep,    i, s) {
  for (i = 1; i+1 in a; i++) {
    s = s a[i] sep
  }
  if (i in a) {
    s = s a[i]
  }
  return s
}

# Join array elements, separated by sep: O(N log N) version
function join2(a, sep,    b, i, j, n) {
  # Copy a into local array "b" and find length "n"
  for (i in a) {
    b[i] = a[i]
    n++
  }
  # Make log(n) passes, joining two strings at a time
  while (n > 1) {
    j = 0
    for (i = 1; i+1 <= n; i += 2) {
      b[++j] = b[i] sep b[i+1]
    }
    if (i <= n) {
      b[++j] = b[i]
    }
    n = j
  }
  # Return final joined string
  return b[1]
}

BEGIN {
  if (ARGC < 3) {
    print "usage: join.awk join1|join2 n"
    exit 1
  }
  s = "The quick brown fox jumps over the lazy dog. "
  for (i=0; i<int(ARGV[2]); i++) {
    s = s s
  }
  print length(s)
  split(s, a)
  if (ARGV[1] == "join1") {
    s = join1(a, " ")
  } else {
    s = join2(a, " ")
  }
  print length(s)+1
}