0

So I was doing this question on Leetcode, where given the inorder and preorder traversal of a binary tree, we have to build the tree. So I wrote the code, and the solution is working, but I am a bit stuck while calculating time complexity of the solution. Could someone please provide an insight into calculating it? Any input is appreciated. Here is the code:

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    def construct(preord, inord, noted):
        if preord == []:
            return

        root = TreeNode(preord[0])
        noted.add(preord[0])
        index = inord.index(preord.pop(0))
        
        for i in inord[index::-1]:
            if preord != [] and i == preord[0]:
                root.left = construct(preord, inord, noted)

        for i in inord[index + 1:]:
            if i in noted:
                break
            if preord != [] and i == preord[0]:
                root.right = construct(preord, inord, noted)
        return root
    
    visit = set()
    root = construct(preorder, inorder, visit)
    return root
Vedant Jadhav
  • 89
  • 5
  • Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Welbog Jun 08 '21 at 13:29

1 Answers1

1

Variable declaration and conditionals have all the same time complexity:

O(1)
This means constant time

Loops or other statements that depend of the quantity of data you have:

O(N)

And if you have nested loops or again statement that depend on the data:

O(n^k)

K being the number of nested levels you have.

Those are not the only ones, here it's an useful link where you can see them all

https://www.bigocheatsheet.com/

Depending of the number of elements you are looping or checking the time incresases or decreases. When we talk about time complexity we need to always put ourselves in the worst case possible.

Imagine you have 1000 numbers, and you want to check if 5 for example is present, you will need to loop through all of them and check.

In the worst case possible your program will need to check all of them, that's why a loop is O(n), n being your 1000 numbers.

Going back to your program, you don't have any nested loops, but you have some for loops, so the Big O of your algorithm is O(n).

You don't need to count the if's or any other statement that takes less than O(n).

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    def construct(preord, inord, noted):
        if preord == []:
            return

        root = TreeNode(preord[0])  //O(1) <--------------------
        noted.add(preord[0])
        index = inord.index(preord.pop(0))
        
        for i in inord[index::-1]:              //O(n) <-------------
            if preord != [] and i == preord[0]:
                root.left = construct(preord, inord, noted)

        for i in inord[index + 1:]:
            if i in noted:             //O(1) <---------------
                break
            if preord != [] and i == preord[0]:
                root.right = construct(preord, inord, noted)
        return root
    
    visit = set()
    root = construct(preorder, inorder, visit)
    return root
Gabri
  • 70
  • 7
  • But do the recursive calls affect the running time complexity? Like in the for loop, the construct function is called whenever the condition is satisfied. In the worst case, it will be called n times, so does that affect the O(n) in any manner? – Vedant Jadhav Jun 08 '21 at 16:22
  • The calculation of recursive time complexities is a bit more complex. There are two theorems that can help you with that, the Master Theorem and the Akra Bazzi Method. You need some level in math in orden to understand them but if you do you will be capable of calculating the time complexity of almost all recrusive algorithms (with some limitations). Here is a good article about the Master theorem https://yourbasic.org/algorithms/time-complexity-recursive-functions/ – Gabri Jun 09 '21 at 07:09