This lesson's interactive features are locked, please to keep using them

Complexity Quiz - Example 3

Consider the following function for two questions:

#  halvedSections returns a list of lists.
#  For example, n=12 results in:
#    [
#       [0 1 2 3 4 5 6 7 8 9 10 11 12]
#       [0 1 2 3 4 5 6]
#       [0 1 2 3]
#       [0 1]
#    ]
def halved_sections(n: int) -> list[list[int]]:
    rows = []
    i = n
    while i > 0:
        col = []
        for j in range(i + 1):
            col.append(j)
        rows.append(col)
        i //= 2
    return rows

It has a specific time complexity of:

T(n) = O(n + n/2 + n/4 + ... 1)

Hint

This is a tricky one. You need to take into account the shrinking size of each successive list.