1

I have written this code that does the job i want it to. What I want to do is figure out the big O notation for the code. So I want to learn how to calculate the time complexity and end up with a big O notation result. How is it done in lay mans terms?

"""

def treetocode(hTree):

    code = dict()
    
    def getCode(hNode, currentcode=""):

        if (hNode == None): return
        if (hNode.left == None and hNode.right == None):
            code[hNode.char] = currentcode
        getCode(hNode.left, currentcode + "0")
        getCode(hNode.right, currentcode + "1")
        if hNode.char == None:
            return None
        else:
            print('Character = {}  :  Freq = {} --- Huffman code {}'.format(hNode.char, hNode.freq, currentcode))

    getCode(hTree)
    return code

"""

NateD0gg83
  • 45
  • 6
  • 1
    May this would hep you (https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation#:~:text=The%20time%20complexity%2C%20in%20Big,n)%20%2C%20often%20called%20linear.)[https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation#:~:text=The%20time%20complexity%2C%20in%20Big,n)%20%2C%20often%20called%20linear] – MrNobody33 Jun 24 '20 at 13:40
  • 1
    See also [Can you confirm the complexity of an algorithm using simulations?](https://stats.stackexchange.com/q/342295/168452) – Håkon Hægland Jun 24 '20 at 13:49
  • Related: [Programmatically obtaining Big-O efficiency of code](https://stackoverflow.com/questions/480775/programmatically-obtaining-big-o-efficiency-of-code); [Determining complexity for recursive functions (Big O notation)](https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation) – wwii Jun 24 '20 at 14:09
  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – wwii Jun 24 '20 at 14:09

1 Answers1

2

Time complexity is unrelated to the language you're using, unless your implementation causes the code to behave differently than the algorithm you have in mind. Since you came up with the algorithm, you can go over the usual steps used to figure out time complexity.

Run the program in your mind. How many times is the function called for every node of the tree? (or whatever structure you have).

Peter
  • 109
  • 5