The shape my mouth makes as I slowly read code and try to calculate that ‘O‘. And apparently there’s also a big omega and theta if you wanna get technical with it?? My brain…
Before I continue, I should probably mention that I’m prepping for my big job hunt using Cracking the Coding Interview by Gayle Laakmann McDowell. It was recommended by several people and although I’m not far in yet, I can see why. It’s well written and there’s a level of confidence you get from the author that hopefully I can eventually achieve in my own writing and coding. Fingers crossed.
Going back to the Big O concept with brothers omega and theta, I’m happy to read that apparently the industry is a bit more ambiguous with its usage of the term big O. That means the finer details you’d find from studying big omega and theta (and what big O should actually define within the bounds of runtime) is most likely something I won’t need to know off the top of my head. I should probably review it anyway when I have a chance, but first comes mastering the basics of big O calculation.
With an oversimplification of the subject, calculating Big O doesn’t seem that difficult. Read through a piece of coding, jot down and section together the time complexity of chunks of the code, then simplify by dropping constants and more insignificant additions to the time calculation (or space if you’re doing Big O for space complexity).
For example: O(2n2+n) =simplifies to=> O(n2)
Yet my mind still manages to make pretzels out of my train of thought as I read code and try to piece together the correct big O. I supposed my bullheaded attempts to understand the code and calculate the time at the same time is not helping.
Well at least I think I got some pointers to keep in mind as I try to master the concept of big O.
- Practice, practice, practice.
- Memorizing concepts like two loops of n length nested is n2 and not nested is n+n isn’t enough and I should make sure I understand the principle by explaining my reasoning either out loud or on paper. (Helpful if you want someone else to understand too)
- Not every variable length is n and two variables of (potentially) different length should get their own variable.
- Learn the typical big O of frequently used data structures and algorithms.
Oh and always think about that Big O for time and space when writing my own code. Even if I’m not some algo/math expert, it’s useful to know if either complexity is horrendous and if there’s space for improvement in the future.
I mean… it would suck if some pigeon was faster than my runtime, right?
Side note. I found a Big-O Cheat Sheet and a place to quiz my Big O knowledge. Time to dust off my coding resources/references folder!