What is the time complexity?
def has_pair(nums):
for a in nums:
for b in nums:
if a != b and a + b == 0:
return True
return FalseOptions
- O(n)
- O(n log n)
- O(n²) (Correct option)
- O(2n)
Answer
O(n²)
Why
For each of the n items in the outer loop, the inner loop runs n times: n × n = n² iterations.
O(n²) is called quadratic: with 1,000 items that is about 1,000,000 checks; with 100,000 items, 10 billion.
A set can solve this specific problem in O(n).
Remember
Loop inside a loop over the same data = O(n²).