Question

Question-6 (10 pts): Study the following Python function and discuss its time complexity, make sure to account for time-cost of calling built-in python methods.

def fun(nums: List[int]):

    number_of_elements = len(nums)

    for index in range(number_of_elements):

        value = nums[index]

        n = nums.count(value)

        print('{v} appeared {n} times'.format(value, n))

Answer 1

Please find the answer for the above given question .

ANSWER :

The time complexity of above given function is O(n^2) [Big O of n square].

The time complexity of len keyword is O(1) [Big O of one].

Here in the given function for loop will run for number of elements that were there in the list that is passed to fun. So if we consider there are n elemets in the list that is passed to fun. So time complexity will be O(n) again.

But inside for loop , we have one keyword which is a count . For that also we have a O(n) time complexity .

So totally it will be O(n^2) [Big O of n square].

Thanks..