Complexity Analysis
def print_upper_triangle(n):
for i in range(n):
for j in range(i, n):
print(i, j)What is the time and space complexity?
Work it out before scrolling down.
Time
O(n²)
Space
O(1)
How to derive it
Inner loop runs (n-i) times for each i. Total iterations: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²). The triangular shape halves the constant but doesn't change the order. No extra data structures, so O(1) space.