0
$\begingroup$

I want to solve a recurrence relation and also be able to determine the height of recurrence relation.

In case of questions that satisfy master theorem the answer in the below link seems to work fine

https://stackoverflow.com/questions/1347909/how-to-determine-the-height-of-a-recursion-tree-from-a-recurrence-relation/64090513#comment139084297_64090513

But in questions like enter image description here

I am unable to figure out if there is a way to define the height of the tree. Also, there is a substitution method in which we substitute the value of n = 3^k and apply log on both side. As in the CLRS book,

enter image description here

but in this case since n is larger the asymptotic correct answer seems to be n for the recurrence. But I am looking for a methodological answer that would satisfy these class of questions. I am wondering if any one could point me out to it. Because here, I can guess since n^1/3 is growing or decreasing a lot faster than 3 so n work but what if there is some constant that grows in same order as n^1/3. Then what would be my asymptotic answer ? Or is there no such constant ?

Please let me know if you any more details from my side. I would be very helpful if someone could give me a methodologial way to find height of this tree and asymptotic bound.

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.