In this blog, I’ll be going a bit further and providing a more in depth of when time complexity comes into play with common examples. We’ll be roleplaying as someone who’s currently in a technical interview and this will give you the gist of what to expect.
Review
The graph presented above is a visual representation of the various time complexities. Keep in mind there are more but to keep things simple we’ll use this graph as a way to “see” and compare complexities.
The Interview
Let’s say the problem they gave you involves searching through a sorted array that contains integers for a specific integer. Easy enough! Just iterate through the array and compare each element with the target element to see if the integer exists and return its index. This is sometimes referred to as the “brute force” method, more on that in a bit. Take a look below at a code example.
As you can see that was pretty simple! In the example we were looking for “4” and given an array with the size of 13, we were able to find the index pretty quickly using a simple for loop to iterate over the array. Now for this case since we had to traverse “4” steps, does that mean our time complexity is “O of 4N” or O(4N)? Sure, you can say that but we typically still refer to it as O(N) because the 4 in front doesn’t mean much to us conceptually or realistically. Almost as if someone asked you,
“how long will it take you to get home?”
“Oh I don’t know, in like 4?”
4 what. 4 seconds, 4 minutes, 4 hours?? This may not be a great example but you get the case, context and eventually scalability matters over time. Let’s say the array size is 1 million. That will certainly take much more time to traverse compared to the size 13. Given this the “hypothetical” time complexity using the function above is still O(N). Take a look at the graph again and you can see that as the input size grows, so does the CPU operations proportionally.
Back to the interview
Alright the interviewer is impressed with your fast wit and quick thinking to come up with a solution to the problem. Though that’s short lived. Suddenly they’re firing off questions left and right,
“What is the time complexity”
“What about its space complexity?”
“Can you make it ‘better’ or ‘faster’ then it currently is?”
“Is this considered a linear search or binary search and if so, can you demonstrate the them?”
“What did I have for breakfast today???”
These are all valid and great questions except that last one. But this illustrates that if you’re not prepared, it can be overwhelming and the main point is not to know everything. Just enough to be on speaking levels conceptually.
Question 1 you know, question 2–4 may be harder if you didn’t study this prior. Lets tacking question 2–4 at the same time.
“Oh yes of course. I can make this better and since it’s a linear search, I’ll implement the binary search method to reduce it from O(N) to O(logN)!”
Bam! you’ve just knocked their socks off and they now they’re officially impressed! You go into explanation of what makes it faster and why it’s considered O(logN). Summing it up to being that the algorithm you came up with effectively splits the big array in half at the first step, checks if the target number is at the middle point and if it isn’t, the algorithm will explore the left or right side. It will continue to chop down the array in half each step until the target number is found. With only 5 minutes to spare you were able to give a solution, provide a working better solution, and explain your knowledge to the interviewer. With a big breath of relief on how well the interview went, your interviewer suddenly drops their smile and asks you to do this recursively. Uh oh.
I hope you all enjoyed the blog this week. And I want to stress that interviewers are not to be feared or trying to fail you. They actually are very kind and will want you to succeed, so asks questions! Lots of questions. I was just being facetious this time. Hope you learned something from this!
