This Week #1: The Big-O no

Big lesson

Last week I listened to a podcast about algorithmic complexity. In the podcast they talked about Big-O notation and what this means running through examples and describing what differences there are (performance-wise). Having not taken a computing course academically I had never been taught about this and in all my previous jobs this has never really come up. Although I had heard the term thrown around here and there I had always shied away from taking the time to learn it. I had convinced myself that this was a complex subject and that I didn't have time to learn about it, after all no one had really raised it as a concern so why would it be a problem?

But after an hour of listening I had been given a brief taste of the Big O notation and really it wasn't as hard as I had built it up in my mind (credit does of course go to the presenters of the podcast who managed to break it down into easy to digest chunks). I had already started to think about places in my code where I was creating potential O(n^2) problems and thinking up ways to solve them.

Small change

So this week I spent some time reviewing some of the code that I knew I had recently written that was going to be a potential problem. After ten minutes a much better solution was in place and whats more I had been given enough information and terminology to explain what the problem was and how the code change addressed it

The problem was that I had two collections. One I had to iterate over, so this is already an O(n) problem. But then for each one of these I was iterating over the second array finding all the instances that matched the same id only to then take the first one returned from that operation.

collection1.map(c1=>collection2.filter(c2=>c2.id===c1.id)[0])

Ok so it's not an O(n^2) problem but it still felt like a problem. And it certainly wasn't an O(n) problem anymore. I could feel that this was creeping into the 'red' zone.

The solution? Change the second array to a standard js key:value object then look up the value as a property.

collection1.map(c1=>collection2[collection1.id])

It wasn't much but I knew that this was now more of an O(n) problem where we should only be going over each array once. And since the first and second collection could each contain hundreds of items it would most likely also prove to be faster.

Next Week and beyond?

I plan to continue to improve my understanding of the Big O notation. At least now I have an appreciation for its purpose as well as breaking through the mental barrier I had put up. I also plan on getting the Big O Cheat Sheet(already on my Christmas list)

p.s podcast was by coding blocks if you haven't already check them out they're well worth a listen too, they run through this and many more programming concepts!