Need help understanding big O

Question

I feel like I have a good grasp on big O from the examples given in my text book, but once I have to figure it out for real functions that I've written myself, I am at a loss. Can anyone help me calculate and understand big O and time complexity/space complexity for the following three functions?

Basically this is just a LeaderBoard class and the leaderboard is formatted as such:

{player_id: [average, [score1, score2, score3...]]...}

here is my code:

class LeaderBoard:
    def __init__(self):
        self.leaderboard = {}

    def add_score(self, player_id, score):
        if player_id in self.leaderboard:
            self.leaderboard[player_id][1].append(score)
            avg = sum(self.leaderboard[player_id][1])/len(self.leaderboard[player_id][1])
            self.leaderboard[player_id][0] = avg
            return avg

        self.leaderboard[player_id] = [score,[score]]
        return score

    def top(self, no_of_top_players):
        top_list = []
        for key,value in sorted(self.leaderboard.items(),key=lambda e:e[1][0], reverse=True):
            top_list.append(key)
        return top_list[:no_of_top_players]

    def reset(self, player_id):
        if player_id in self.leaderboard:
            self.leaderboard[player_id][0] = 0
            self.leaderboard[player_id][1] = []

Answer 1

Here is a (almost) line by line analysis of your code, showing the complexity of (almost) each line. To get the total complexity of a method, you normally take the biggest complexity that appears inside that method.

def add_score(self, player_id, score):
    """
    Time complexity of this method is 'O(k)', where 'k' is the number of scores that
    the specified 'player_id' has.
    """
    if player_id in self.leaderboard:               # O(1)      membership check in dict
        player = self.leaderboard[player_id]        # O(1)      get item from dict
        score_list = player[1]                      # O(1)      get item from list
        score_list.append(score)                    # O(1)      list append

        sum_score_list = sum(score_list)            # O(len_score_list) list sum
        len_score_list = len(score_list)            # O(1)      list length
        avg = sum_score_list / len_score_list       # O(1)      int division
        player[0] = avg                             # O(1)      assignment
        return avg                                  # O(1)      return

    new_data = [score, [score, ]]                   # O(1)      lists creation
    self.leaderboard[player_id] = new_data          # O(1)      assigment
    return score                                    # O(1)      return

def top(self, no_of_top_players):
    """
    Time complexity of this method is 'O(n log n)', where 'n' is the number players.
    """
    sorted_player_list = sorted(                    # O(n log n) list sort
        self.leaderboard.items(),
        key=lambda e: e[1][0], reverse=True)

    top_list = []                                   # O(1)      list creation
    for key, value in sorted_player_list:
        top_list.append(key)                        # O(n)      list append n times

    top_list = top_list[:no_of_top_players]         # O(no_of_top_players) list slice
    return top_list                                 # O(1)      return

def reset(self, player_id):
    """
    Time complexity of this method is 'O(1)'.
    """
    if player_id in self.leaderboard:               # O(1)      membership check in dict
        player = self.leaderboard[player_id]        # O(1)      get item from dict
        player[0] = 0                               # O(1)      assignment
        player[1] = []                              # O(1)      list creation and assignment

I hope this gets you started in the right direction to analyse your code in the future.