Here are some of the most common Time Complexity mistakes I’ve seen candidates make in interviews I’ve conducted:

1. Assuming Constant Time for Certain Operations

Incorrect Assumption

Believing that built-in functions or operations in modern programming languages are always O(1) (constant time) because they are provided for convenience.

Example

Using the index function to find the position of an element in an array or string.

my_list = [1, 2, 3, 4, 5]
position = my_list.index(3)  # O(1) or O(|my_list|)?

Why It's Incorrect

Even though functions like index are built-in and convenient, they are not O(1) operations. The computer still has to iterate over the data to locate the element, resulting in an O(N) time complexity, where N is the length of the list or string. Similarly, operations like insert, delete, or remove on lists or arrays have O(N) time complexity because they require shifting elements.

Do It Right

Always analyze the time complexity of built-in functions and operations based on their underlying implementations. Do not assume they are O(1) without verification.

____________________________________________

Btw, let me introduce myself: I'm an ex-FAANG Senior Software Engineer who has conducted hundreds of coding interviews, currently on sabbatical. You can get free daily coding interview tips from me straight to your inbox by subscribing to my newsletter called Faangshui here: blog.faangshui.com. Let's also connect on Linkedin! Now let's get back to the common mistakes...

____________________________________________

2. Saying O(N) Without Defining What N Is

Incorrect Assumption

Stating that an algorithm has a time complexity of O(N) (or something else) without specifying what N represents.

Why It's Incorrect

Time complexity is expressed in terms of the size of the input, but without defining N, it's unclear what variable or parameter N refers to. This can lead to misunderstandings and incorrect analysis.

Do It Right

Before stating the time complexity, clearly define what N represents in the context of the problem. For example, if N is the length of an array, or the number of nodes in a tree, specify that. This ensures clarity and accuracy in your analysis.

3. Saying O(N²) When There Are Actually Two Different Variables

Incorrect Assumption

Simplifying time complexity to O(N²) (or some other function only mentioning N) when the algorithm depends on two different input sizes, effectively combining them into a single N.

Example

def compare_lists(list1, list2):
    for item1 in list1:
        for item2 in list2:
            if item1 == item2:
                print(f"{item1} is in both lists")

Why It's Incorrect

If list1 has length N and list2 has length M, the total number of iterations is N × M. Stating the time complexity as O(N²) assumes N = M, which may not be the case.

Do It Right

Use distinct variables to represent different input sizes. In this case, the time complexity should be expressed as O(N × M). Do not reduce multiple variables to a single N unless they are guaranteed to be of the same size.

4. Ignoring Recursive Call Costs

Incorrect Assumption

Overlooking the cost of recursive calls in both time and space when analyzing recursive algorithms.

Example

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Why It's Incorrect

Each recursive call adds a new layer to the call stack, consuming both time and space. Ignoring these costs leads to underestimating the algorithm's complexity.

Do It Right

Account for the number of recursive calls and the work done in each call. For the factorial function, there are O(N) recursive calls, each performing O(1) work, resulting in O(N) time complexity. Additionally, the space complexity is O(N) due to the call stack depth.

5. Counting Input Data in Space Complexity

Incorrect Assumption

Including the input data's size in the space complexity when it is provided as a parameter and not modified.

Example

# Is space complexity O(N) or O(1)?
def exists(elements, target):
    for e in elements:
        if e == target:
             return True
    return False

Why It's Incorrect

Space complexity measures the additional memory used by the algorithm, excluding the input data that is already provided. Counting the input data in the space complexity can overstate the algorithm’s space requirements.

Do It Right

Don’t include the input data’s space when calculating space complexity unless the algorithm makes a copy or significant modification. Only account for the extra space used by the algorithm, such as auxiliary variables or data structures.

6. Assuming String Operations Are O(1)

Incorrect Assumption

Believing that operations on strings are O(1) because a string is stored as a single data element.

Example

# O(1) or O(N)?
def isEqual(s1, s2):
    return s1 == s2

Why It's Incorrect

Strings are sequences of characters, similar to arrays. Operations that involve scanning or modifying strings—such as comparing them or searching for a character—have time complexities that depend on the length of the string, typically O(N), where N is the size of the string.

Do It Right

Recognize that strings are collections of characters. When performing operations like searching, slicing, or concatenation, consider the length of the string in your time complexity analysis.

7. Assuming You Can Ignore a Variable Because It's Small

Incorrect Assumption

Neglecting a variable in time complexity analysis because it is considered small compared to another variable.

An algorithm has a time complexity of O(N × M), where N can be up to 25 and M can be up to 1,000,000. Assuming N is small, one might simplify the complexity to O(M).

Why It's Incorrect

Even if N is smaller than M, it still varies (not constant!) and impacts the algorithm's performance. Ignoring N can lead to underestimating the time complexity, especially if N increases.

Do It Right

Include all variables that can vary in your time complexity analysis, regardless of their relative sizes. Express the complexity in terms of all relevant variables, such as O(N × M), to accurately represent the algorithm's performance.

Time Complexity is a Cheat Code

Time complexity analysis is a powerful tool, but it’s easy to overlook key details or make assumptions that lead to incorrect conclusions.

Did you know you can actually use time complexity analysis as the biggest hint during your interviews? I wrote how to do it here: https://blog.faangshui.com/p/every-problem-has-a-cheat-code

________________________________________________________________________

If you don't want to miss daily algorithms and coding interview tips, insights and deep dives like this, consider subscribing to my free Faangshui newsletter: https://blog.faangshui.com/

Thanks!