It’s been about a year since I started to work for Spotify. That time I wrote a few articles about my job search experience. Among others, I shared how much I underestimated the importance of complexity analysis and the big-O notations when it comes to senior roles. My assumption was that knowing the space and time complexities of the different algorithms and operations on different data structures isn’t something important. Dealing with such issues is rare in most jobs. Still, asking about complexities might be an easy way to rate someone’s knowledge when it comes to candidates with no or short experience. On the other hand, when you’re looking for experienced people, there should be many other more meaningful ways to understand someone else’s skills. I still think that this is true, but I also realized that many big (and small) companies just go with the standard questions involving complexity analysis. Therefore, finally, I collected some complexities and some tips to learn them. Communication over end results The end result of your complexity analysis is important. Yet, it’s secondary. It doesn’t differ from other interview questions in this sense. The most important is clear communication. You have to share your thread of thoughts partly because it proves how good a communicator you are and partly because sharing your thoughts is insurance against your mistakes. If you have a mistake in your analysis, you’ll still show that otherwise, your thinking was right. Whereas if you simply share a result and it’s bad, you failed to share anything positive at all. This is even more important if you know that you have holes in your knowledge - just like me. When you start analyzing a problem, tell what you know for sure and share the assumptions you have and start your analysis from there. Most probably you’ll understand how loops are composed, how they (don’t) add up if they are sequential and how they influence the complexity of an algorithm if they are nested. At the same time, most probably there will be some container manipulations - either directly or through some standard functions - within the loops and you might lack some knowledge regarding the complexity of those calls. Sharing your assumptions will at least balance a bit of that lack of knowledge. In the worst case, you’ll have a useful discussion with your interviewer. When I was interviewing for a position at a code analysis company, I clearly failed the interview due to my lack of knowledge in this field, but at least I learned a few tips about how to approach complexity analysis in future interviews, which clearly helped me get an offer from Spotify. How to learn If you want to learn complexity analysis, you might just revisit your CS studies where most probably it was covered in detail. An even better option with less fluff is to take a book such as Cracking the Coding Interview and start reading it thoroughly and solving its exercises on a regular basis. Ideally, you’d spend some time on it every day or at least once or twice a week. Even if you don’t plan to interview in the near future. Or maybe especially if you don’t plan to interview in the near future! I don’t know about you, but I’m not a university student anymore who can pull in one-nighters just to pass an exam and forget about what I learned hoping that I won’t need that crap for the rest of my life. You never know what tomorrow will bring. Maybe you get laid off the next day, or you just realise that it’s time to leave. Then it’ll be a bit late to start preparing. It’s better if you have already started your preparation! But as I said many times, most people are lazy and disorganized. So what to do if you need to improve your complexity analysis skills as soon as possible before a C++ coding interview? identify the most important time/space complexities you should know go on the C++ Reference pages of the identified functions and methods and start memorising the complexities spend some time on this activity every day, consistency will do miracles even better if you revisit your CS basics when you learn about a complexity so that you understand why inserting into a std::map has the complexity of O(log n). This will both make it easier for you to succeed in general complexity analysis tasks and it’ll also make you realize that it’s not so difficult to learn it, you just need some time. In the next sections, I’ll help you collect the most fundamental complexities. Notions Before we get into discussing complexities, let’s remind ourselves about the different notions. O(1) stands for constant complexity, meaning that the complexity doesn’t depend on the input size, it’ll always be about the same. A variation of constant complexity is amortized constant complexity. It means that the runtime will be much slower once in a while, but very rarely, so overall, on average, that slowdown is amortized so we can still talk about a constant complexity. Linear complexity O(n) means that as the input size grows, the necessary amount of operations grows the same way. On the other hand, when we talk about logarithmic complexity O(log n), the number of operations that need to be executed grows much slower than the input size. When it comes to C++ standard containers and algorithms, these are the three notions that we use. Still, it’s good to remind ourselves that there are also quadratic and exponential complexities. When we talk about quadratic complexity O(n^2), the number of required operations is about the squared size of the input. That’s quite bad. But not as bad as the exponential complexity O(2^n) where by each additional input element the necessary time or space doubles. (While there are other complexities, these are the most widely used ones.) Containers and operations First, let’s see what are the most important containers you’ll likely deal with in a coding interview, what are the underlying data structures and what are the related complexities. My goal is not to give you a deep analysis, just to provide you with the most necessary information, then you can do your own research. std::array std::array is a fixed-size array, storing objects in contiguous memory locations. accessing the first element: with front() which has a complexity of O(1) accessing the last element: with back() which has a complexity of O(1) accessing a random element: with at() or with operator[] both have a complexity of O(1) std::list std::list is a container that supports fast insertion and removal, but doesn’t support fast random access. It is usually implemented as a doubly-linked list. std::forward_list is similar, but implemented with a singly-linked list, so it’s more space efficient, but it supports iteration only in one direction accessing the first element: with front() which has a complexity of O(1) accessing the last element: with back() which has a complexity of O(1) (not supported by std::forward_list) accessing a random element: not supported inserting at the front: with push_front() which has a complexity of O(1) inserting at the back: with push_back() which has a complexity of O(1) (not supported by std::forward_list) inserting at a random location: with insert() which has a complexity of O(1) for one element, and complexity of O(n) for multiple elements, where n is the number of elements to be inserted (insert_after for std::forward_list) removing an item from the front: with pop_front() which has a complexity of O(1) removing an item from the back: with pop_back() which has a complexity of O(1) (not supported by std::forward_list) removing an item from a random location: with erase() which has a complexity of O(1) for one element, and a complexity of O(n) for multiple elements, where n is the number of elements to be erased (erase_after for std::forward_list) std::vector std::array is a dynamically sized sequence container, where the elements are stored contiguously. Random access is cheap, as well as operations at the end, unless reallocation is required. accessing the first element: with front() which has a complexity of O(1) accessing the last element: with back()