Complexity

Warning: this is technical and potentially quite tedious.

The “technical quiz” I mentioned in the previous post was received on Saturday night. Initially it seemed to be a straightforward, simple, problem solving exercise. I had to write a program that took a couple of files as input, process them, and produce some output. Proper computing! Of course, once I got involved in the task I realised that it was a lot more complex than it appeared and was going to involve difficult sums and everything. It’s been a while since I’ve dabbled with discrete mathematics and so it took some time to acclimatise. To cut a long and extremely tedious story short, I was reminded of why algorithmic complexity matters and how much difference it makes. In a nutshell I initially solved the problem with an O(nn) algorithm. It worked, and produced the correct results, but extending the input set to around 20 made it unfeasible, even on a fast machine:

2020 = 104857600000000000000000000

After some gentle prodding from my inquisitors I realised that there already existed many solutions to the same problem, discovered by some very clever bastards, that solved exactly the same problem in far more efficient ways. The best was in O(n3). This means that running the same 20 set took less than a second:

203 = 8000

What does this mean ? Well to me, it means:

  • Big numbers are confusing, even to smug gits like me who think they understand them.
  • Cryptanalysis is hard.
  • Wizards really do exist, but they call themselves Mathematicians.
  • I will never understand math(s), but I’ll always love it.

This task kept my brain busy and I thoroughly enjoyed it. It was like giving my brain a little shower. Now I’ve finished it there’s a big hole in my cerebral process table, and I feel a little bit hollow.

Humph’s health deteriorated this weekend and so today we had to take her for another visit to the vets in Cherry Hill. She’s fighting through it though, like the tough little bird she is. But the worry of that, combined with some sad news from my homeland, and the gap left by the technical problem, are making me feel a little low.

It’ll pass.


Leave a Reply