Stop Making These Time Complexity Mistakes!
Avoid These Common Time Complexity Traps in Your Next Interview
Analyzing time complexity is a fundamental skill in coding interviews, but many candidates make avoidable mistakes that can lead to incorrect conclusions and hurt their performance. Let’s dive into some of the most common errors 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.
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 FalseWhy 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 == s2Why 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.
Summing Up
Time complexity analysis is a powerful tool, but it’s easy to overlook key details or make assumptions that lead to incorrect conclusions. By avoiding these common mistakes and thinking critically about both time and space complexity, you’ll be well-equipped to accurately assess algorithms in coding interviews.
Stay curious and happy coding!
Nurbo
Need Help with Coding Interviews?
Are you struggling with coding problems or feeling unprepared for your upcoming interviews? You're not alone, and I'm here to help.
With years of experience as a coding interview coach, I offer personalized one-on-one sessions to:
Master problem-solving skills for coding and system design interviews
Boost your confidence for the big day
Develop effective strategies to level up your tech career
Ready to elevate your coding interview skills? Book a personalized 1:1 coaching session with me today!
Still have questions? Let's chat! You can book a free 30-minute consultation to discuss how I can help you achieve your goals.
Feel free to email me at nurbo.kusmagul@(google’s email service) or connect with me on LinkedIn.
Looking forward to helping you succeed!