CODEWITHSUNDEEP
pythonalgorithmrecurrence
Mod
Mod

Reputation: 65

Recurrence relation and time complexity of finding next larger in Generic tree

Question: Given a generic tree and an integer n. Find and return the node with next larger element in the tree i.e. find a node with value just greater than n.

Although i was able to solve it is O(n) by removing the later for loop and doing comparisons while calling recursion. I am bit curious about time complexity of following version of code.

I came up with recurrence relation as T(n) = T(n-1) + (n-1) = O(n^2). Where T(n-1) is for time taken by children and + (n-1) for finding the next larger (second for loop). Have i done it right? or am i missing something?

def nextLargestHelper(root, n):
"""
root => reference to root node
n => integer
Returns node and value of node which is just larger not first larger than n.
"""
# Special case
if root is None:
    return None, None
# list to store all values > n
largers = list()
# Induction step
if root.data > n:
    largers.append([root, root.data])
# Induction step and Base case; if no children do not call recursion
for child in root.children:
    # Induction hypothesis; my function returns me node and value just larger than 'n'
    node, value = nextLargestHelper(child, n)
    # If larger found in subtree
    if node:
        largers.append([node, value])
# Initialize node to none, and value as +infinity
node = None
value = sys.maxsize
# travers through all larger values and return the smallest value greater than n
for item in largers: # structure if item is [Node, value]
    # this is why value is initialized to +infinity; so as it is true for first time
    if item[1] < value:
        node = item[0]
        value = item[1]
return node, value

Upvotes: 1

Views: 120

Answers (1)

Duda
Duda

Reputation: 3736

At first: please use different chacters for O-Notation and inputvalues.

You "touch" every node exactly once, so the result should be O(n). A bit special is your algorithm finding the minimum afterwards. You could include this in your go-though-all-children loop for an easier recurrence estimation. As it is, you have do a recurrence estimation for the minimum of the list as well.

Your recurrence equation should look more like T(n) = a*T(n/a) + c = O(n) since in each step you have a children forming a subtrees with size (n-1)/a. In each step you have next to some constant factors also the computation of the minimum of a list with at most a elements. You could write it as a*T(n/a) + a*c1 +c2 which is the same as a*T(n/a) + c. The actual formula would look more like this: T(n) = a*T((n-1)/a) + c but the n-1 makes it harder to apply the master theorem.

Upvotes: 1

Related Questions