How can I reduce time complexity on this algorithm?

October 26, 2022

I have this exercise and the goal is to solve it with complexity less than O(n^2).

You have an array with length N filled with event probabilities. Create another array in which for each element i calculate the probability of all event to happen until the position i.

I have coded this O(n^2) solution. Any ideas how to improve it?

probabilityTable = [0.1, 0.54, 0.34, 0.11, 0.55, 0.75, 0.01, 0.06, 0.96]

finalTable = list()

for i in range(len(probabilityTable)):
    finalTable.append(1)
    for j in range(i):
        finalTable[i] *= probabilityTable[j]

for item in finalTable:
    print(item)

>Solution :

probabilityTable = [0.1, 0.54, 0.34, 0.11, 0.55, 0.75, 0.01, 0.06, 0.96]

finalTable = probabilityTable.copy()

for i in range(1, len(probabilityTable)):
    finalTable[i] = finalTable[i] * finalTable[i - 1]

for item in finalTable:
    print(item)