What is the time and space complexity of my algorithm?

user_19315537 0
Viewed 39


As I am learning data structure and algorithms, I am very confused about computing the complexity of time and space of the algorithm.

This problem is from the leetcode.

def product_except_self(nums):
    result = []
    start = 0
    while start != len(nums):
        total = 1
        for i in nums:
            if i != nums[start]:
                total *= i
        result.append(total)
        start += 1
    return result

So, my computation complexities are,
Time Complexity: O(n^2)
Space Complexity: O(n)

data-structures complexity-theory time-complexity algorithm
1 Answers
def product_except_self(nums):
    result = [] // in the worst case you would need to put all array in the result array, what give O(n) space complexity. 
    start = 0
    while start != len(nums): // O(n) complexity
        total = 1
        for i in nums: // One more loop that gave additional O(n) complexity, in result we have O(n^2)
            if i != nums[start]:
                total *= i
        result.append(total)
        start += 1
    return result

Yep, you have the correct assumption

user_17648030
Related