What is the time complexity of a loop followed by a nested loop?
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).
Verify This Answer
Cross-check this information using these trusted sources:
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.
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).
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).
Still have questions?
Browse all our FAQs or reach out to our support team