Jake has come up with a way to perform an O(n) operation outside of a loop, or function calling, which allows a version of this problem (for c99 only) that supports the full 32 bits.

1
2
3
4
5
6
7

void nLogNRecursive (int n) {
   if (n != 0) {
     int filler[n] = {0};
     nLogNRecursive (n / 2);
     nLogNRecursive (n / 2);
  }
}

It exploits the fact that array initialisation is an O(n) operation. Congratulations Jake for being smarter than me =)

Now that the semester is drawing to a close, a fellow tutor and I were discussing some cool puzzles and other activities we could get our students to think about.

We came up with a creative programming puzzle that went something along the lines of this:

Without using any loops, helper functions, IO, unstructured control, global or static variables, write a function with the prototype:

void nLogNRecursive (unsigned int n)

of complexity n log n, where n is the integer passed into the function. You may specify the range of valid inputs for n, but make it as large as you can.

Here is my solution.

I started by considering the two parts of a typical n log n function - the O(n) operation, and the recursive delegation into each half of the input.

1
2
3

orderNOp(n);
nLogNRecursive(n/2);
nLogNRecursive(n/2);

Right, having done this, this meant that somehow I would have to implement an O(n) operation using the same function that was meant to perform an O(n log n) operation! Somewhat difficult.

My first approach was a bit crap, as it drastically reduced the range of possible n inputs. I treated the first (little-end) half of the input integer as the actual input, and if the second half was non-zero, would delegate recursively using the first half number. If the second half was not-zero, then I would ignore the first half and decrement the second half recursively until it hit zero. This way, depending on which half of the integer was set, I determined my behavior:

0x0010|0000 -> perform O(n) operation for n = 17
0x0000|0010 -> perform O(n log n) operation for n = 17

Essentially, I used bitwise operations to cram two arguments into the one integer. Here's the full solution for this approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//Solution 1. Crappy Shorts
#define first(n) (n & 0xFFFF)
#define second(n) ((n & ~0xFFFF) >> 16)
#define to_s(n) (n << 16)

void nLogNRecursive (unsigned int n) {
   if (second(n) == 0) {
      if (first(n) > 1) {
         nLogNRecursive(to_s(first(n)));
         nLogNRecursive(first(n)/2);
         nLogNRecursive(first(n)/2);
      }
   } else {
      if (second(n) > 0) {
         nLogNRecursive(to_s(second(n)-1));
         constant();
      }
   }
}

This works okay, I guess, but the question asks us to maximize our input size. Seeing as the function only works with one working copy of n at a time (either n from which we subtract one, or n which we divide by two), we could use 31 bits of the integer to represent our n, and just the most significant (and least often used) bit of the integer to be a boolean flag as to which n we are using. Here's the updated solution, and, I think, the best way to solve this problem. Please comment if you discover a better way, preferably one that sacrifices no bits.

Still, this gives you the same positive range as a signed int, which is pretty big.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//Solution 2. 31 Bits

#define deflag(n) (n & (~ (1 << 31)))
#define enflag(n) (n | ( 1 << 31) )
#define flag(n) (n & (1 << 31))

void nLogNRecursive2 (unsigned int n) {
   if (flag(n) == 0) {
      if (n > 1) {
         nLogNRecursive2(enflag(n));
         nLogNRecursive2(n/2);
         nLogNRecursive2(n/2);
}
   } else {
      if (deflag(n) > 0) {
         nLogNRecursive2(enflag(deflag(n)-1));
         constant();
      }
   }
}

Please comment if you think of a better way!