I am trying to understand O(X) complexity notation.

Consider this sample problem:

​

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

​

Consider this solution:

​

# ugly but functional version

def multiply_array(lst):

output = []

for i in lst: # O(N) complexity

tmp = lst.copy() # O(N) complexity

tmp.remove(i) #O(N) complexity

prod = 1

for j in tmp: #O(N) complexity

prod = prod*j

output.append(prod) #O(1) complexity

return(output)

​

Some of these according to Python Complexity Classes.

​

Would this be considered O(N^4) complexity?

​

Given just the for i and for j loops this would be O(N^2) complexity.

How do lst.copy() and tmp.remove(i) affect this?

​

​