Company: OPTUM
Difficulty: medium
Algorithm Analysis Question 1 Coding Test How to Attempt? Your friend Mathew has come up with an algorithm to solve a complex problem on the trees. Him being poor in analysis of algorithms, asks you to analyze his algorithm and tell the number of operations it will take to solve the problem using the given algorithm on an arbitrary tree with N(≥ 0) nodes. You have been given the following information: Let T(N) be the number of operations that are required by the algorithm to solve the problem for an arbitrary tree of size N. Then, we define T(N) as, T(N) = T(N/3) + 2 * T(N/2) + 5N for all N ≥ 4 T(N) = 1 for all N Your task is to find and return the value of T(N) after modulo with 10 9 +7. Note: Here the division operator is integer division operator i.e., it divides two numbers and returns the integer part of the result. Input Specification input1: An integer N, denoting the number of nodes in the tree Output Specification Return the value of T(N) after modulo with 10 9 +7 Examples Exa