sean's place

Complexity Analysis

Last night, I decided a problem I was having at work wasn’t worth solving.

Why?

Because the only algorithm that I could think of at the time was O(N^2), and on a medium to large-sized data set, the processing time was astronomical. I implemented my algorithm, and sure enough, astronomical only began to describe the glacial pace of the data processing.

Then, I had an inspiration. Use a hash.

New implementation: O(N). Processing time for an ~81,000 item data set: 1.17 seconds on a Pentium 4-M 2.20GHz.

Actually, this solution had come to me before. I had just written it at 24,000 feet on my way to Seattle. I had just forgotten about it in the meantime. The problem: analyze and link the free-form comments from the inventory table for “Wiki-fication” of any nested part numbers to their appropriate tuples.