The answer
If a loop iterates over Array A (size N) and a nested loop iterates over Array B (size M), the time complexity is O(N * M), not O(N^2).
How to Calculate Time Complexity in an Interview
How do I calculate the complexity of two different inputs?
More FAQs in How to Calculate Time Complexity in an Interview
Identify all loops. Add sequential loops together. Multiply nested loops. Expose the complexity of built-in methods, and drop non-dominant terms and constants.
It is O(N) + O(N^2). Since N^2 is the dominant term that scales the fastest, the final time complexity is strictly O(N^2).
No, Big O calculates the worst-case scenario. Even if an if-statement breaks the loop on the first try, the algorithm is still classified as O(N).
Still have questions?
Browse all our FAQs or reach out to our support team
Want to upskill yourself?
Your learning library
Small steps. Big possibilities.
Find your next course. Build something great.