Runtime Analysis in Algorithm Interviews

Part of an algorithm interview is coding up the "best" answer as quickly as possible. There are a number of ways to quantify best, clean code, well explained, and of course worst case runtime are important. Worst case runtime is signified by "Big Oh" or O(x) notation as a function of the length of the inputs.

There are ways to approach problems to find the fastest solution in its runtime, but in this post, we're looking merely to analyse what we've already written. In the majority of cases, while mentioning the expected runtime might be ok during coding, a deeper dive into the analysis isn't necessary until after the code is completely written.

The first thing to do is to identify the inputs and their dimensions. Oftentimes, you have a single list of length n. But be sure there aren't tricky added variables like number of digits of each number in the list. In tree type problems, you may need to express the final result in terms of both n (the total nodes in the tree), as well as o (level order, the height of the tree).

Then analyse the code as you've written it. Your intentions don't matter at this stage, the code is done, and functional. How does it perform? Watch out for nested loops, list comprehension within a list, and magic methods. Sometimes a built in method will operate in O(n) time, when it doesn't look like it. If you're changing datatypes in a loop, you may run into this type of issue. Consider:

def problem(inputdict):
  for k,v in inputdict.iteritems():
    templist = list(inputdict.keys)

This isn't the best formulation of how to solve the problem, so let's analyze what's wrong. We're iterating over the dictionary, and then getting a list of keys. So the outer loop is O(n), and the templist line is also O(n). Multiplying, we get O(n^2). These types of small one liners are quite insidious, especially in python. It's easy to write a casual single line that has bad runtime analysis.

In this situation, don't go back and refactor the code. Make note of the problem, give a quick statement of what you'd do to fix it, and continue analysing the runtime. In this case, the total runtime is O(n^2).

Let's dive into a solution and look at its runtime. We don't need to know what the solution is solving in order to analyse the runtime. We just need to know what the input is, and that's shown here.

def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    output = [1] * len(nums)
    top = 1
    bottom = 1
    for i in range(len(nums)):
        j = len(nums) - i - 1
        output[i] *= top
        output[j] *= bottom
        leftNum = nums[i]
        rightNum = nums[j]
        top *= leftNum
        bottom *= rightNum
    return output

Here we see on the first line the muliplication creates an array, and will be O(n) in the length of nums. The next few are constant assignment. Then we get to the main loop. We know the loop will be O(n) for each of the internal lines. Now we can just inspect each of those to confirm each are constant time, also known as O(1). Taking a look over each, all are arithmetic operators on primitive variables. So they're all constant. Great. The overall runtime of the entire method is O(n).

Trees can get a bit more complex. But here's an exercise for a tree problem. Try it out before reading the solution.

class Solution(object):
    def validHelper(self, root, maxVal, minVal):
        if not root:
            return True
        cur = True
        if root.left:
            if root.val <= root.left.val or (minVal != None and minVal >= root.left.val):
                return False
            cur = cur and self.validHelper(root.left, root.val, minVal)
        if root.right:
            if root.val >= root.right.val or (maxVal != None and maxVal <= root.right.val):
                return False
            cur = cur and self.validHelper(root.right, maxVal, root.val)
        return cur
        
        
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.validHelper(root, None, None)

Tree problems are often seen in recursive situations. In this case, you have to understand the runtime on each node, and then the growth of the recursive calls. Which nodes in the tree are being called and how many times. Let's start with each call.

This is a binary tree, and we don't have access to any other part of the tree as we process it. So looking at the assignment and comparison code here, we can see we don't access any variables more than a countable number of times (the opposite of countable would be in a loop, or by another call to the method). The two assignments show us that we call the recursive helper method for each the left and right trees. We can further see that as we traverse downwards, we'll get a single boolean value, either from the base case or from the recursive case. There's no way for moving back up the tree except through the standard call stack. This means each node in the tree will be called exactly once.

With each being called once, and each call taking constant time, the overall runtime will be O(n).