Complexity Analysis
def all_pairs(arr):
pairs = []
n = len(arr)
for i in range(n):
for j in range(n):
pairs.append((arr[i], arr[j]))
return pairsWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n²)
Space
O(n²)
How to derive it
Outer loop runs n times, inner loop runs n times for each outer iteration: n × n = n² iterations. Each iteration does O(1) work. The output list stores n² pairs. Time and space are both O(n²).