CODEWITHSUNDEEP
pythonoptimizationhash
Mario Danov Ivanov
Mario Danov Ivanov

Reputation: 1

Determining time complexity of a function

I have a computer science project in which i am tasked to assess the time complexity of this specific function and also figure out a way to optimize it by using hash function data structures like sets and dictionaries.

def uber_friends(group, network, current_user):        
    if  current_user not in group:                 
        group.append(current_user)
        for x in range(0, len(network)):
            if current_user in network[x]:
                ind = network[x].index(current_user)  
                if ind == 0:
                    uber_friends(group, network, network[x][1])
                if ind == 1:
                    uber_friends(group,network, network[x][0])
    else:
        return None

    return group

For clarification "group" is supposed to be an empty list at first, network is supposed to be a nested list in which the elements inside the inner lists are 2 ints and current_user is supposed to be an int Edit: typo

Upvotes: 0

Views: 215

Answers (1)

Samwise
Samwise

Reputation: 71522

A good first step in figuring out the time complexity of a function is to run it with some sample input -- we can then trace through the function and see where the execution might be spending its time.

uber_friends([], [], 1)

    uber_friends([], [], 1)
  File "test.py", line 2, in uber_friends
    if current_user not in grumo:
NameError: name 'grumo' is not defined

This exception is raised on the first line of the function, and will be raised regardless of what parameters are passed. The time complexity of the function is therefore O(1).

We could simplify the implementation down to a single line that behaves the same as the original recursive function:

def uber_friends(group, network, current_user):
    raise NameError("name 'grumo' is not defined")

but this does not affect the time complexity. Further optimization involving different data structures is neither possible nor necessary.

Upvotes: 2

Related Questions