DSA

def prefix_average1(S):
    n = len(S)                      # O(1)
    A = [0] * n                     # O(n)
    for j in range(n):
        total = 0                   # O(n)
        for i in range(j + 1):
            total += S[i]           # O(1 + 2 + ... + n) = O(0.5 * n^2 + 0.5 * n) = O(n^2)
        A[j] = total / (j + 1)      # O(n)
    return A                        # O(1)

# T(n) = O(1) + O(n) + O(n) + O(n^2) + O(n) + O(1) = O(n^2)

def prefix_average2(S):
    n = len(S)                          # O(1)
    A = [0] * n                         # O(n)
    for j in range(n):
        A[j] = sum(S[0:j+1]) / (j+1)    # O(n^2), see the breakdown below:

        # subset = S[0:j+1]               O(j + 1), for j = 0, 1, 2, ..., n - 1 = O(1 + 2 + ... + n) = O(0.5 * n^2 + 0.5 * n) = O(n^2)
        # total = sum(subset)             O(j + 1) = O(n^2)
        # count = j + 1                   O(1) * n = O(n)
        # average = total / count         O(1) * n = O(n)
        # A[j] = average                  O(1) * n = O(n)

    return A                            # O(1)

# T(n) = O(1) + O(n) + O(n^2) + O(1) = O(n^2)

def prefix_average3(S):
    n = len(S)                  # O(1)
    A = [0] * n                 # O(n)
    total = 0                   # O(1)
    for j in range(n):
        total += S[j]           # O(1) * n = O(n)
        A[j] = total / (j + 1)  # O(1) * n = O(n)
    return A                    # O(1)

# T(n) = O(1) + O(n) + O(1) + O(n) + O(n) + O(1) = O(n)