Skip to main content

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like .

For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting algorithm A takes 1, 2, 4, 16, 32, and so on seconds to sort 1, 2, 3, 4, 5, and so on elements and sorting algorithm B takes 1, 2, 3, 4, 5, and so on seconds for the same. The former algorithm would be considered exponential time or O(2^n) and the latter linear time O(n). Note that exponential time is really bad because for just 30 elements, you'd be talking about 12,427 hours of compute time. Instead of actually measuring the execution time of an already implemented algorithm, we can calculate a rough model for it via asymptotic notation.

First, to analyze the complexity of algorithms, there is a need to be precise: Are you interested in complexity in the worst case or average case? There is also best case performance, but you touch that less frequently. Some algorithms such as quicksort have good average cases (O(n log n) for quicksort) but poor worst case (O(n^2)). For interviews, usually the interviewer is interested in worst-case complexity, but if in doubt, ask. Before going further, let's get a good working definition of the most common form complexity analysis: Big O notation. Big O is the asymptotic upper bound of the growth of complexity.

Some common Big-O classes are, in the order of efficiency: O(1) constant < O(log n) logarithmic < O(n) linear < O(n log n) < O(n^2) quadratic < O(n^3) cubic < ... < O(2^n) exponential < ... < O(n!) factorial.

"Big-O" Class Name Representative algorithms
O(1)constant-timeinsertion into a linked list, lookup of a hash table with no collisions
O(log n)logarithmic-timebinary search on sorted array
O(n)linear-timelinear search, counting sort, iterate thru array a constant number of times, Boyer-Moore string search
O(n log n)quasilinear timemergesort, heapsort worst case, quicksort avg case, comparison-based sort, Dijkstra's shortest path (nonnegative edge weights)
O(n^3)cubic-timeFloyd-Warshall all-pairs shortest-path algorithm, Bellman-Ford
O(n^k)polynomial-timedynamic programming
O(2^n)exponential-timebacktracking algorithm
O(n!)factorial-timebrute-force search traveling salesman

Continue to part 2.


Popular posts from this blog

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and eve…

Interview Gotchas

It's a challenge to outperform all the other candidates in a competitive tech job only, but there is hope. You can improve your performance with practice and watching out for these gotchas: Make absolutely sure you are solving the right problem: I ran into this the other day. It is entirely a communication issue. When doing an initial screen over the phone, this problem is compounded. For example, maybe an interviewee is hacking out a function that returns the k highest priced products when the interviewer is expecting the kth highest priced product. One can squander a lot of time due to these misunderstandings. A good interviewer will try to guide you back to the right path, but you can't expect this. Be sure to ask questions. Confirm that the input and output are exactly what you expect. Use examples.Don't ever give an interviewer the impression that you are avoiding writing real code. This is an impression thing. This is a coding interview so you should be expecting to…