CODEWITHSUNDEEP
pythonalgorithmbig-o
bighead
bighead

Reputation: 135

calculating big o of my function

I am learning about Big O and need some help calculating the big O of my function.

I need to find out the big O if self is of size s and other is of size o

I am not sure about the complexity of calling the has function as i know the for loop in intersection will be complexity of S

but will the complexity of has() be of size o? as id imagine it having to loop through o until it finds a match or returns false.

The data types of self and other that are being used are positive and negative ints

 def has(self, item):

        return item in self.items

    def intersection(self, other):
        common = Set()
        for item in self.items:
            if other.has(item):
                common.add(item)
        return common

Upvotes: 1

Views: 176

Answers (1)

Łukasz Rogalski
Łukasz Rogalski

Reputation: 23203

Time complexity for checking if value is in list would be O(n) (it'll have to loop). Time complexity for checking if value is in set would be O(1) - it'll compute a hash and check whether there is a value for this hash in a set. You may write your own class that implements in where time complexity would be related to your own implementation. You cannot answer this question without knowing definition of other.

Upvotes: 1

Related Questions