retagged by
8,622 views

1 Answer

7 votes
7 votes

You see, the important point to note in this recurrence relation is that there are two unequal recursive calls. That's the reason behind my choice of solving this recurrence relation using recursion tree method.

Another point to note here is that the cost of cost of combining the solution at the top most level of the tree is $n$. At the lower level of tree the cost is computed by adding the value of $n$ at each level. 

Since the first recursive call takes $1/5th$ of the total input and the second call takes $7/5th$ of the total input, the two sub-tree(left sub-tree and right subtree) will not have same height. But here we can make a sloppy assumption that it is a complete binary tree with $log_{10/7}n$ levels, this will help us in computing the upper bound of the tree.

HTH

Related questions

0 votes
0 votes
1 answer
1
1 votes
1 votes
1 answer
2
1 votes
1 votes
2 answers
3
mdboi asked Oct 28, 2022
781 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n